Hints

Recall that

2^0 + 2^1 + 2^2 + ... 2^(n - 1) = 2^n - 1

Hence, while solving bitset problems, remember that

The i-th bit alone is more powerful than all lower bits combined.

Hence, if you had an opportunity to make 10000...(n times) vs 111....(n times), you can clearly see that the combined power of 111... doens’t match the smallest number with the i-th bit. Hence, if you get the opportunity to set the i-th bit in the resulting bitwise AND, you should always do it, regardless of how badly it might affect the lower order bits.

Of course, if the i-th bit is set in all of the elements, then we don’t need to do anything. Else, we need to turn on that bit in all elements. What is the cost to do so (assume that there are no higher order bits than bit).

Notice that the operation is increasing a[i] by 1 each step. Hence, if the current number is val, we need to reach 2^i by taking one step each. Why not any number greater than 2^i? Becuse we arae taking one step at a time, hence, we would reach 2^i first since that is the smallest number with that bit set.

What is the cost required?

val + cost = 2^i
cost = 2^i - val

Hence, we will pay a cost of 2^i - val and convert a[i] to 2^i. What happens when we are not able to convert some a[i]?

If you are not able to pay the cost of some a[i], then you should revert the cost and overwrites of previous a[i] for that bit since the cost can be utilized for lower order bits.

But this approach is only for the bit b with the assumption that all the bits greater than b would be zero. What if they are not? The cost formula is incorrect in that case, and we can’t just overwrite it with 2^i?