MYSARA Video Solution

Bro we can’t draw a correct conclusion after comparing no. of set bits.
Correct algo is as follows:
we have to iterate over bit string of Bi for i=1 to n-1, to check the possibility of existence { Ai }
–> if the jth bit is on than jth bit of B(i+1) should also be 1, otherwise answer would be 0. Because if
any bit is 1 it can’t be 0 after taking bitwise OR .
Or simply we can deduce that the above point is same as the condition Bi & B(i+1) == Bi.
After checking this condition we can simply multiply 2^(no. of set bits in bi).

for eg:-

  1. {2,6,7}
    bit representation of 2= “10”.
    Since the 2nd bit of 2 is 1 thus 2nd bit of 6 should also be 1. That is true. So ans*=2^(1).
    Same process for 6(“110”). 2nd and third bit of 6 is 1 and also 7 has 2nd and 3rd bit set. So the condition is true. Thus ans*=2^(2). And finally ans=8.
  2. {3,13}
    Answer is 0, in spite of the fact that set bits of 3 are less than 13. Because 2nd bit of 3 is 1
    but 14’s 2nd bit is off, which isn’t possible after taking bitwise OR. Thus answer is simply 0.
1 Like