3133. Minimum Array End - Explanation

Description

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 operation between all elements of nums is x.

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

Example 1:

Input: n = 3, x = 2

Output: 6

Explanation: nums can be [2,3,6].

Example 2:

Input: n = 5, x = 3

Output: 19

Explanation: nums can be [3,7,11,15,19].

Constraints:

1 <= n, x <= 100,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We need to build an array of n elements where the AND of all elements equals x, and the array is strictly increasing. The smallest such array starts with x as the first element. Each subsequent element must be greater than the previous one and still have x as a subset of its bits (so the AND remains x).

To find the next valid number after res, we add 1 and then OR with x. Adding 1 ensures the number increases, and ORing with x ensures all bits of x are set (preserving the AND property).

Algorithm

Initialize res = x.
Repeat n - 1 times:
- Set res = (res + 1) | x.
Return res.

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res = x
        for i in range(n - 1):
            res = (res + 1) | x
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Representation And Bit Manipulation

Intuition

The brute force iterates n - 1 times, which is too slow for large n. Instead, we can directly compute the answer using bit manipulation. The key insight is that the answer must have all bits of x set, and we need to "count" to n - 1 using only the bit positions where x has 0s.

Think of it as embedding the binary representation of n - 1 into the zero-bit positions of x. The bits of x stay fixed at 1, while the zero positions of x are filled with the bits of n - 1 in order.

Algorithm

Convert x and n - 1 to binary arrays.
Iterate through bit positions of x:
- Skip positions where x has a 1.
- For positions where x has a 0, fill in the next bit from n - 1.
Convert the resulting binary array back to an integer.
Return the result.

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

        x_bin = [0] * 64  # Binary representation of x
        n_bin = [0] * 64  # Binary representation of n-1

        for i in range(32):
            x_bin[i] = (x >> i) & 1
            n_bin[i] = (n >> i) & 1

        i_x = 0
        i_n = 0
        while i_x < 63:
            while i_x < 63 and x_bin[i_x] != 0:
                i_x += 1
            x_bin[i_x] = n_bin[i_n]
            i_x += 1
            i_n += 1

        for i in range(64):
            if x_bin[i] == 1:
                res += (1 << i)

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

3. Bit Manipulation

Intuition

We can optimize further by avoiding explicit binary arrays. Using bit masks, we iterate through bit positions. For each zero-bit position in x, we check if the corresponding bit in n - 1 is set, and if so, set that bit in our result.

We use two pointers: one for positions in the result (i_x) and one for bits of n - 1 (i_n). Whenever we find a zero-bit in x, we potentially copy a bit from n - 1 to the result.

Algorithm

Initialize res = x.
Use two bit masks: i_x iterates through bit positions of the result, i_n iterates through bits of n - 1.
While i_n <= n - 1:
- If bit position i_x in x is 0:
  - If the current bit of n - 1 (checked via i_n & (n-1)) is set, set this bit in res.
  - Shift i_n left (move to next bit of n - 1).
- Shift i_x left (move to next bit position).
Return res.

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        res = x
        i_x = 1
        i_n = 1  # for n-1

        while i_n <= n - 1:
            if i_x & x == 0:
                if i_n & (n - 1):
                    res = res | i_x
                i_n = i_n << 1
            i_x = i_x << 1

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Using 32-bit Integers Instead of 64-bit

The result can exceed the range of a 32-bit integer. Since we are embedding the bits of n-1 into the zero positions of x, the result can grow significantly larger than both n and x. Always use long, long long, Int64, or BigInt depending on your language to avoid overflow and incorrect results.

Misunderstanding Which Bits to Fill

The algorithm fills the zero-bit positions of x with the bits of n-1, not n. A common mistake is using n directly, which gives an off-by-one error in the result. Remember that we need the (n-1)th valid number after x in the sequence, so we embed the binary representation of n-1, not n.

Confusing the AND Constraint with OR

The problem requires that the AND of all array elements equals x, meaning every element must have all bits of x set to 1. Some solutions mistakenly treat this as an OR constraint. When constructing the answer, you must OR with x (or only modify zero-bit positions of x) to ensure the AND property is preserved across all elements in the sequence.