824. Under the Ceiling, Above the Floor

A rack holds n devices; device i draws a[i] watts. Two adjustments are available, and each may be used on any device any number of times:

a device drawing an EVEN number of watts may be HALVED a device drawing an ODD number of watts may be DOUBLED

Every device must end up drawing at least F watts, the level below which it stops working. Print the smallest ceiling M such that every device can be brought into the range F .. M, or -1 if no ceiling works.

devices 1 2 3 4, F = 1 -> 3 devices 4 8 16, F = 3 -> 4 devices 4 8 16, F = 5 -> -1 devices 3 5, F = 1 -> 5

## What one device can reach

Doubling an odd value makes it even, and halving that even value returns it to where it started, so no sequence ever gets past the following simple picture. Let

y = 2 * a[i] when a[i] is odd y = a[i] when a[i] is even

Then the reachable values of device i are exactly y, y/2, y/4 and so on, stopping at the first odd one. That is a CHAIN, at most about 31 values long, sorted downward, and no value outside it is ever reachable.

So the whole problem is: pick one value from each chain so that all the picks lie in a common window whose bottom is F.

## The check, which is a small algorithm rather than a comparison

For a candidate ceiling M, each device independently wants the LARGEST value in its chain that is at most M, because the larger it is the better its chance of also clearing F. Walking the chain finds it:

cur = y while cur > M and cur is even: cur = cur / 2 if cur > M: this device cannot get under the ceiling at all if cur < F: it gets under the ceiling only by going below the floor otherwise: this device is satisfied

The loop stops at an odd value because an odd value cannot be halved. The device fails exactly when that odd value is still above M.

## Why the predicate is monotone

Raise M by one. The largest chain value at most M either stays the same or becomes larger, never smaller, so a device that was above F stays above F, and a device that could not get under the old ceiling may now manage it. So feasibility never turns off as M rises, and the workable ceilings form a suffix. The answer is the first one.

## The bounds, and when the answer is -1

lo = F, since the ceiling cannot be below the floor.

hi = 2 * max(a), the largest value any chain contains. Nothing above it can help, because every chain already has a value at or below it.

Test hi before the loop. If even the loosest ceiling fails, no ceiling works and the answer is -1. The third example is the case: the chain of 4 is 4 2 1, all of it below a floor of 5, so no window with bottom 5 can ever contain a value of that device.

## Why the loop terminates

mid = lo + (hi - lo) / 2 gives lo <= mid < hi, so every branch strictly narrows the range. About 31 iterations for watts up to 10^9.

## Overflow

2 * max(a) reaches 2 * 10^9, which still fits in a signed 32-bit integer, so the type looks safe. lo + hi reaches 4 * 10^9, which does not. This is the same trap as problem 811 and the same cure: write the midpoint as lo + (hi - lo) / 2.

## Cost

Time O(n log(max a) log(max a)): one binary search over the ceiling, and a chain walk per device inside each step. Space O(n).

Constraints - `1 ≤ n ≤ 50000` - `1 ≤ F ≤ 1000000000` - `1 ≤ a[i] ≤ 1000000000`