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