I am unable to find the recurrence relation .how to solve this using bitmask?

Consider a sequence of n bits of which (i-1) are occupied.

u have a total of i cases,

Case 1: first i-1 bits are occupied => 1 way ->time = i seconds

Case 2: first i-2 bits are occupied , (i-1)th bit is not occupied,

here you have (n-i+1) possibilities for the last bit => (n-i+1) ways ->time (i-1) seconds

Case 3: first i-3…, (i-2)th bit not occupied ,and 2 bits among (i-1)th to nth bit are occupied ,so there are (n-i+2)c2 ways…

.

.

.

so on.

U get summation of this pattern divided by total no of ways to assign i bits among n bits that is nCi

Time complexity : O (n^2 ) ,Sufficient for the given constraints

I didn’t get that .

Can you paste the link of your solution?

thanks

Nice Explanation

Thanks brother