Minimum Array End

MEDIUM✓ CHIP-TIMEDLC #3133 — FULL STATEMENT ↗

The drill: Build the smallest possible last element of a strictly increasing array of n positive integers whose bitwise AND all comes out to x — every entry has to carry all of x's bits and nothing forces the rest.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two positive integers arrive: n, a count, and x, a bit pattern every element of a hidden array must respect. The array holds exactly n distinct positive integers in strictly increasing order, and ANDing all of them together must equal x exactly.

Among every array that satisfies those rules, the task is to report the smallest possible value its last, largest element could take.

Every element must carry all of x's set bits, since an AND can never gain a bit that even one element lacks — but the positions where x is 0 are unconstrained and free to differ between elements, as long as the array keeps increasing strictly.

EX 01

n = 1 · x = 4

→ 4

N = 1, THE ARRAY IS JUST [X]

EX 02

n = 2 · x = 7

→ 15

X ALREADY HAS EVERY LOW BIT SET, SO THE FREE SLOT IS HIGHER UP

EX 03

n = 3 · x = 2

→ 6

SEVERAL FREE BIT POSITIONS BELOW AND ABOVE X'S BIT

n and x are positive integers, and n can grow very large
the hidden array always has exactly n strictly increasing positive entries
the AND of the entire hidden array is fixed to equal x exactly
only the minimum possible last element is asked for, not the full array

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Simulating the array by hand — starting at x, always stepping up to the next number that still carries every bit of x — finds the right answer, but the count n can be enormous.

HINT 2 THE STRUCTURE

Every element only needs to agree with x on the bits x already has set; the bit positions where x is 0 are completely free to vary between elements and still keep the AND correct.

HINT 3 ONE STEP FROM THE ANSWER

Treat n − 1 in binary and pour its bits, one by one from the lowest, into x's zero-bit slots, skipping any position x already occupies. What's left is the minimum last element.

COACH'S BOARD — THE PATTERN, STEP BY STEP

BITS INTO THE GAPSPATTERN · SPREAD BITS INTO GAPSn = 3 · x = 2

X / N-1 / RESULT (BINARY)

x → 2 (010)

n-1 → 2 (10)

result → 2 (010)

STEP 1

x=2 already owns bit position 1, the 2's place — that bit is frozen. n−1 = 2 (binary 10) pours its own bits into the free slots, lowest gap first.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-array-end.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        result = x
        bit = 0
        while n:
            while result & (1 << bit):  # skip bit positions x already occupies
                bit += 1
            if n & 1:
                result |= 1 << bit
            bit += 1
            n >>= 1
        return result

TIME O(LOG N + LOG X)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        current = x  # the smallest value whose bits already cover x
        count = 1
        while count < n:
            current += 1
            while (current & x) != x:  # keep climbing until x's bits are all present again
                current += 1
            count += 1
        return current

TIME O(N · GAP)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public long minEnd(int n, int x) {
        long remaining = n - 1;
        long result = x;
        int bit = 0;
        while (remaining != 0) {
            while ((result & (1L << bit)) != 0) { // skip bit positions x already occupies
                bit++;
            }
            if ((remaining & 1) != 0) {
                result |= (1L << bit);
            }
            bit++;
            remaining >>= 1;
        }
        return result;
    }
}

TIME O(LOG N + LOG X)SPACE O(1)JAVA · RACE PACE · 18 LN

class Solution {
    public long minEnd(int n, int x) {
        long current = x; // the smallest value whose bits already cover x
        int count = 1;
        while (count < n) {
            current++;
            while ((current & x) != x) { // keep climbing until x's bits are all present again
                current++;
            }
            count++;
        }
        return current;
    }
}

TIME O(N · GAP)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED