# Hints

`bit`

. Assume that all bits higher then position `bit`

are set to zero.
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`

?

`a[i]`

. Then, the assumption that there are no set bits after `bit`

will always hold.
`a[i]`

to reach `2^i`

, iterate over each `a[i]`

and keep subtracting the cost.