Minimum Array End

Problem Description

You are given two integers n and x. You need to construct an array of positive integers nums of size n where:

• nums[i] < nums[i + 1] for all 0 ≤ i < n - 1 (i.e. the array is strictly increasing).
• The bitwise AND of all elements of nums is x.

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

Examples

Constraints

• 1 ≤ n, x ≤ 10⁸

Map the Bits of (n - 1) Into x’s Zero Positions

For the bitwise AND of the array to be x, every element in the array must have all the bits of x set. That is, if a bit is 1 in x, it must be 1 in every element.

To construct the strictly increasing array:

1. The first element is x itself.
2. For subsequent elements, we want to increment the value while keeping all 1 bits of x locked. This means we are free to change only the bits that are 0 in x.
3. To find the nth element (which corresponds to n - 1 increments starting from index 0), we take the binary representation of n - 1 and map its bits into the 0 bit positions of x.

For example, if x = 4 (100 in binary) and n = 3 (n-1 = 2, which is 10 in binary):

• The 0 positions in x (from right to left) are at indices 0 and 1.
• We map the bits of 2 (10 in binary) into these positions:
  • Bit 0 of 2 (0) goes to index 0.
  • Bit 1 of 2 (1) goes to index 1.
• The resulting value is 110 in binary, which is 6.

Solution: Bit Placement

class Solution {
    public long minEnd(int n, int x) {
        long result = x;
        long remaining = n - 1;

        // iterate through the bits of result, placing bits of remaining into 0 spots
        for (int i = 0; i < 64 && remaining > 0; i++) {
            if ((result & (1L << i)) == 0) {
                // if bit i of x is 0, place the lowest bit of remaining here
                if ((remaining & 1) != 0) {
                    result |= (1L << i);
                }
                remaining >>= 1;
            }
        }
        return result;
    }
}

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        result = x
        remaining = n - 1

        # place bits of remaining (n - 1) into the 0 bits of x
        i = 0
        while remaining > 0:
            if (result & (1 << i)) == 0:
                if remaining & 1:
                    result |= (1 << i)
                remaining >>= 1
            i += 1

        return result

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x;
        long long remaining = n - 1;

        for (int i = 0; i < 64 && remaining > 0; i++) {
            if ((result & (1LL << i)) == 0) {
                if (remaining & 1) {
                    result |= (1LL << i);
                }
                remaining >>= 1;
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(log N + log X). The loop runs at most 64 times since we look at 64-bit representations.
• Space Complexity: O(1).

Where it breaks: the return value must be long (Java) or long long (C++). Even though n and x are both bounded by 10⁸ (which fits in a standard 32-bit signed integer), mapping the bits of n - 1 into the zero spots of x shifts bits up to index 62, which exceeds the 32-bit integer range. Returning a 32-bit integer causes overflow.

← All Problems