Minimum Array End

How it works

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.

Steps

1. Initialize res = x.
2. Use two bit masks: i_x iterates through bit positions of the result, i_n iterates through bits of n - 1.
3. 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).
4. Return res.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

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.

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

class Solution {
public:
    long long minEnd(int n, int x) {
        long long res = x;
        long long i_x = 1;
        long long 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;
    }
};