Minimum Array End

Difficulty: Hard Source: NeetCode

Problem

You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND of all elements of nums is x.

Return the minimum possible value of nums[n - 1].

Example 1: Input: n = 3, x = 4 Output: 6 Explanation: The array [4, 5, 6] has AND = 4 & 5 & 6 = 4, and the last element is 6.

Example 2: Input: n = 2, x = 7 Output: 15 Explanation: The array [7, 15] has AND = 7 & 15 = 7, and the last element is 15.

Constraints:

1 <= n <= 10⁸

1 <= x <= 10⁸

Prerequisites

Before attempting this problem, you should be comfortable with:

Bitwise AND (&) — a bit is 1 only if it is 1 in all operands
Bit masking — using a mask to isolate or embed bits in specific positions
Bit construction — building a number by placing bits into chosen positions

1. Brute Force (Greedy Iteration)

Intuition

The AND of all elements must equal x. That means every element must have at least the bits of x set — any element with a 0 in a position where x has a 1 would break the AND constraint.

So every array element must be a “superset” of x’s bits: it has all of x’s bits set, plus potentially some extra bits.

To minimize the last element, we want the array to grow as slowly as possible. Start with x itself (the smallest number with exactly x’s bits), then count up through numbers that still have all of x’s bits set. We need to pick n such numbers; the last one is our answer.

For n = 3, x = 4 = 100:

Numbers with bit 2 set: 4 (100), 5 (101), 6 (110), 7 (111), 12 (1100), …
First 3: [4, 5, 6] → last element = 6

For n = 2, x = 7 = 111:

Numbers with all 3 lowest bits set: 7 (0111), 15 (1111), 23 (10111), …
First 2: [7, 15] → last element = 15

This works but can be slow for large n since we iterate one by one.

Algorithm

Initialize current = x.
Repeat n - 1 times:
- Increment current by 1.
- Use OR to ensure all bits of x are still set: current = current | x.
Return current.

Solution

def minEnd(n, x):
    current = x
    for _ in range(n - 1):
        current = (current + 1) | x
    return current


print(minEnd(3, 4))  # 6
print(minEnd(2, 7))  # 15
print(minEnd(1, 5))  # 5   (array of one element: [5])
print(minEnd(3, 7))  # 23  ([7, 15, 23])

Complexity

Time: O(n) — too slow for n up to 10⁸
Space: O(1)

2. Bit Embedding (O(log n))

Intuition

The brute force insight was that array elements must have all of x’s bits set, plus any additional bits in the “free” positions (bit positions where x has a 0). Those free positions are where we do our counting.

The crucial realization: as we step through valid numbers (all having x’s bits set), the free bits count in binary from 0 upward. The k-th valid number (0-indexed) has exactly the binary representation of k embedded into the free bit positions of x.

We want the (n-1)-th valid number (0-indexed), so we need to embed the binary representation of n - 1 into the free bit positions of x.

Example: n = 2, x = 7 = 0111

Free bits: position 3, 4, 5, … (anywhere x has a 0)
We want the 1st valid number (0-indexed), so embed 1 = ...001 into free bits.
Position 3 is the first free bit. Place the bit 1 of (n-1) = 1 there.
Result: 0111 | 1000 = 1111 = 15 ✓

Example: n = 3, x = 4 = 100

Free bits: positions 0, 1, 3, 4, … (anywhere x has a 0)
Embed n-1 = 2 = 10 into free bits. We need 2 free bits.
- Free bit 0 (position 0): embed bit 0 of 2 = 0
- Free bit 1 (position 1): embed bit 1 of 2 = 1
Result: 100 | 010 = 110 = 6 ✓

Example: n = 3, x = 7 = 111

Free bits: positions 3, 4, 5, …
Embed n-1 = 2 = 10 into free bits.
- Free bit 0 (position 3): embed bit 0 of 2 = 0
- Free bit 1 (position 4): embed bit 1 of 2 = 1
Result: 00111 | 10000 = 10111 = 23 ✓

The algorithm scans through all bit positions. When it finds a 0 in x (a free position), it takes the next bit from n - 1 and places it at that position in the result.

Algorithm

Let m = n - 1 (the index of the element we want, 0-based).
Start with result = x.
Scan bit positions from 0 upward, tracking two separate bit indices:
- i — current bit position in the final result
- j — current bit position in m
While m >> j > 0 (there are still bits to embed from m):
- If bit i of x is 0 (it’s a free position):
  - Extract bit j of m and place it at position i of result.
  - Advance j to the next bit of m.
- Advance i to the next bit position.
Return result.

Solution

def minEnd(n, x):
    m = n - 1         # We want the (n-1)-th element, 0-indexed
    result = x
    i = 0             # bit position in result / x
    j = 0             # bit position in m (n-1)

    while m >> j:     # while there are still bits to embed from m
        if not (x >> i & 1):  # if position i is a free bit (0 in x)
            # Place bit j of m into position i of result
            result |= ((m >> j) & 1) << i
            j += 1
        i += 1

    return result


print(minEnd(3, 4))   # 6
print(minEnd(2, 7))   # 15
print(minEnd(1, 5))   # 5
print(minEnd(3, 7))   # 23
print(minEnd(5, 3))   # 15  ([3,7,11,13,15])

Complexity

Time: O(log n + log x) — we scan through bits of both n and x
Space: O(1)

Common Pitfalls

Not understanding why (current + 1) | x works in the brute force. Adding 1 to current may clear some of x’s bits (e.g., if there’s a carry into a set bit of x). ORing with x restores all of x’s required bits, jumping to the next valid number that has all of x’s bits set.

Confusing “free bits” with “zero bits”. A “free bit” is a position where x has a 0. These positions can be freely set to 0 or 1 in array elements without breaking the AND constraint. x’s 1-bits are “locked” — they must be 1 in every element.

Off-by-one on the index. We want the (n-1)-th element (0-indexed) because the first element is index 0 (which is x itself). Embed n - 1 into the free bits, not n.

Large n values. For n up to 10⁸, the brute force O(n) loop would run 100 million iterations. The bit embedding approach runs in about 58 iterations (log₂(10⁸) ≈ 27 bits for m, plus up to 27 locked bits in x, ≤ 54 iterations total), which is orders of magnitude faster.

Keyboard shortcuts

Note Book