Skip to main content
CodePeetCodePeet
CodePeet 250

Minimum Array End

MEDIUMProblemSolveExternal Links

Description

Given two positive integers n and x, your task is to build a strictly increasing array of n positive integers where the bitwise AND of every element in the array produces x.

Formally, construct an array nums of size n such that:

  • For every 0 <= i < n - 1: nums[i + 1] > nums[i] (strictly increasing)
  • The bitwise AND of all elements equals x: nums[0] AND nums[1] AND ... AND nums[n-1] = x

Return the minimum possible value of nums[n - 1] (the last element of the array).

Examples

Example 1

Input: n = 3, x = 4

Output: 6

Explanation: One valid array is [4, 5, 6]. Each element is larger than the previous, and their bitwise AND is 4 & 5 & 6 = 100 & 101 & 110 = 100 = 4, which equals x. No valid array of size 3 whose AND is 4 can have a last element smaller than 6.

Example 2

Input: n = 2, x = 7

Output: 15

Explanation: One valid array is [7, 15]. In binary: 7 = 0111 and 15 = 1111. Their AND is 0111 & 1111 = 0111 = 7, which equals x. To maintain the AND at 7 (requiring all three lower bits to be set), every element must have those bits. The next integer after 7 with all three lower bits set is 15 (binary: 1111).

Constraints

  • 1 ≤ n, x ≤ 10^8

Editorial

Brute Force - Consecutive ORing

Intuition

The most natural way to approach this problem is to build the array element by element and see what the last element turns out to be.

A critical observation: for the AND of all elements to equal x, every bit that is set to 1 in x must be set to 1 in every element of the array. If even one element has a 0 where x has a 1, the AND would produce a 0 in that bit position, violating the requirement.

This means the smallest valid first element is x itself — any smaller positive integer would necessarily have at least one of x's bits missing.

Now we need to find the next n - 1 elements. To get the next element, we increment our current value by 1 (ensuring the array stays strictly increasing) and then apply a bitwise OR with x. The OR step is the clever part: incrementing might flip some bits that x needs, and ORing with x restores them. This guarantees every element retains all of x's required bits.

By repeating this increment-then-OR process n - 1 times, the final value of result is the minimum possible last element.

Step-by-Step Explanation

Let's trace through with n = 3, x = 4:

Step 1: Initialize result = x = 4 (binary: 100). This is the first element of our array. We need to generate 2 more elements.

Step 2: Iteration 1 — Increment: result = 4 + 1 = 5 (binary: 101). We now have a candidate that is strictly greater than 4.

Step 3: Iteration 1 — OR with x: result = 5 | 4 = 101 | 100 = 101 = 5. Bit 2 (the required bit from x = 4) was already present in 5, so the OR changes nothing. The second element is 5.

Step 4: Iteration 2 — Increment: result = 5 + 1 = 6 (binary: 110). Next candidate.

Step 5: Iteration 2 — OR with x: result = 6 | 4 = 110 | 100 = 110 = 6. Bit 2 is already present in 6. The third element is 6.

Step 6: All 3 elements generated: [4, 5, 6]. Verify: 4 & 5 & 6 = 100 & 101 & 110 = 100 = 4 = x ✓. Return 6.

Brute Force — Building the Sequence by Consecutive ORing — Watch how we build the strictly increasing array element by element, using increment and OR with x to generate each valid number.

Algorithm

  1. Set result = x (the first and smallest valid element)
  2. Repeat n - 1 times:
    • Increment result by 1
    • Set result = result | x to restore any bits from x that may have been lost during the increment
  3. Return result

Code

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x;
        for (int i = 0; i < n - 1; i++) {
            result = (result + 1) | x;
        }
        return result;
    }
};
class Solution:
    def minEnd(self, n: int, x: int) -> int:
        result = x
        for _ in range(n - 1):
            result = (result + 1) | x
        return result
class Solution {
    public long minEnd(int n, int x) {
        long result = x;
        for (int i = 0; i < n - 1; i++) {
            result = (result + 1) | x;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop executes exactly n - 1 iterations. Each iteration performs one addition and one OR operation, both of which are O(1). The total work is therefore directly proportional to n.

Space Complexity: O(1)

Only a single variable (result) is used to track the current value. No additional data structures are needed, so memory usage is constant regardless of input size.

Why This Approach Is Not Efficient

The brute force performs n - 1 iterations, each doing constant work. With n up to 10^8, this means up to 100 million operations. While each operation is lightweight (an addition and an OR), 10^8 iterations can take several seconds and will exceed typical time limits.

The fundamental inefficiency is that we construct every intermediate element of the array, even though we only care about the last one. We compute element 1, then element 2, then element 3, all the way to element n - 1 — discarding each intermediate value immediately.

Key insight that enables a faster approach: The valid numbers form a predictable pattern in binary. Every valid number looks like x but with some of x's zero-bit positions filled in. The sequence of valid numbers is equivalent to counting 0, 1, 2, 3, ... but spreading those counter bits across x's zero positions only. So the n-th valid number (the answer) is simply x with the binary representation of n - 1 placed into its zero-bit positions. This is a direct calculation that takes O(log n) time — no loop over n needed.

Optimal Approach - Bit Position Mapping

Intuition

Instead of building every element one by one, we can jump directly to the answer using bit manipulation.

Here is the key observation: for the AND of all elements to equal x, every bit that is 1 in x must remain 1 in every element. These are fixed bits — they cannot vary across the array. The only bits we are free to change are positions where x has a 0. These are free bits.

Think of x's binary form as a template with locked and unlocked slots. For example, x = 6 (binary: 0110) locks bit 1 and bit 2 at 1, while bit 0 and bit 3 are free. Any valid number in our array must match the pattern _11_ where underscores can be 0 or 1.

The valid numbers in increasing order are those formed by counting through the free bit positions: 0110 (6), 0111 (7), 1110 (14), 1111 (15). Notice the free bits cycle through values 00, 01, 10, 11 — that is just counting from 0 to 3 in binary!

So the n-th valid number (0-indexed) corresponds to the counter value n. Since we want element n - 1 (the last of n elements, 0-indexed), we need to spread the bits of n - 1 into the free positions of x. This gives us a direct O(log(n + x)) calculation.

Diagram showing how bits of n-1 are mapped into the zero-bit positions of x to form the result
Diagram showing how bits of n-1 are mapped into the zero-bit positions of x to form the result

Step-by-Step Explanation

Let's trace through with n = 4, x = 6 (binary: 0110):

Step 1: Initialize result = x = 6 (binary: 0110). Compute n - 1 = 3 (binary: 11). Set mask = 1 (starting at bit position 0). The fixed bits of x are at positions 1 and 2. The free bits are at positions 0, 3, 4, and beyond.

Step 2: Examine bit 0 (mask = 1): x's bit 0 is 0 — a free position. Take the LSB of remaining = 3 (binary: 11): the LSB is 1. Set bit 0 in result: result = 0110 | 0001 = 0111 = 7. Right-shift remaining: 3 >> 1 = 1.

Step 3: Examine bit 1 (mask = 2): x's bit 1 is 1 — a fixed position. We cannot modify this bit. Skip. The mask advances but no bit from remaining is consumed.

Step 4: Examine bit 2 (mask = 4): x's bit 2 is 1 — another fixed position. Skip again.

Step 5: Examine bit 3 (mask = 8): x's bit 3 is 0 — free position found! Take the LSB of remaining = 1 (binary: 1): the LSB is 1. Set bit 3 in result: result = 0111 | 1000 = 1111 = 15. Right-shift remaining: 1 >> 1 = 0.

Step 6: remaining = 0, so all bits of n - 1 have been placed. The loop terminates.

Step 7: Result = 15. Verify: the array [6, 7, 14, 15] is strictly increasing and 6 & 7 & 14 & 15 = 0110 & 0111 & 1110 & 1111 = 0110 = 6 = x ✓.

Bit Position Mapping — Placing n-1 Bits Into Free Positions of x — Watch how the bits of n-1 are spread into x's zero-bit positions, directly computing the answer without iterating through all intermediate values.

Algorithm

  1. Set result = x and remaining = n - 1
  2. Initialize mask = 1 (starting at the least significant bit)
  3. While remaining > 0:
    • If the current bit position in x is 0 (i.e., (mask & x) == 0):
      • If the LSB of remaining is 1, set this bit in result (result |= mask)
      • Right-shift remaining by 1 (consume one bit from n - 1)
    • Left-shift mask by 1 (move to the next bit position)
  4. Return result

Code

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x;
        long long remaining = n - 1;
        long long mask = 1;
        while (remaining > 0) {
            if ((mask & x) == 0) {
                result |= (remaining & 1) * mask;
                remaining >>= 1;
            }
            mask <<= 1;
        }
        return result;
    }
};
class Solution:
    def minEnd(self, n: int, x: int) -> int:
        result = x
        remaining = n - 1
        mask = 1
        while remaining > 0:
            if (mask & x) == 0:
                if remaining & 1:
                    result |= mask
                remaining >>= 1
            mask <<= 1
        return result
class Solution {
    public long minEnd(int n, int x) {
        long result = x;
        long remaining = n - 1;
        long mask = 1;
        while (remaining > 0) {
            if ((mask & x) == 0) {
                result |= (remaining & 1) * mask;
                remaining >>= 1;
            }
            mask <<= 1;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log(n + x))

The while loop runs until remaining (initially n - 1) becomes 0. Each time we encounter a free bit position in x, we right-shift remaining, halving it. So remaining reaches 0 after at most log₂(n) free-position encounters. The mask also scans through the bits of x, which contributes at most log₂(x) iterations. The total number of loop iterations is bounded by the number of bits needed to represent max(n, x), giving O(log(n + x)).

In practice, since n and x are both bounded by 10^8 (roughly 27 bits), the loop runs at most about 60 iterations — effectively constant time on fixed-width integers.

Space Complexity: O(1)

Only three variables (result, remaining, mask) are used. No additional data structures are allocated, so memory usage is constant regardless of input size.