Problem editorial

Minimum Array End

MediumBit Manipulation PatternsBit ManipulationArrayMath

Minimum Array End: the approach in brief

The problem

Implement Solution.minEnd(n, x) to determine the smallest possible final value of an array of n positive integers.

Pattern

Minimum Array End is a Bit Manipulation Patterns problem, in the Bitwise Operations - Power of Two/Four Check subpattern. The pattern covers xOR tricks, counting bits, power-of-two checks, and Hamming weight

Approach outline

Because the first element is `x`, every other element must preserve all bits that are set in `x`.
Think of the required sequence as assigning increasing binary patterns to the bit positions where `x` has zeroes.
The index of the final element is `n - 1`; its binary representation determines which available zero-bit positions must be turned on.

Complexity

The reference solution runs in O(log answer) time and O(1) space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Minimum Array End and the problems around it

Minimum Array End is a Bit Manipulation Patterns problem, in the Bitwise Operations - Power of Two/Four Check subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Minimum Array End