LeetCode 3133 - Minimum Array End

The problem asks us to construct a strictly increasing array nums of length n such that the bitwise AND of all elements equals x. Among all valid arrays, we want to minimize the last element, nums[n - 1]. The constraints are important: - Every element must be a positive integer.

leetcodemediumbit-manipulation

LeetCode Problem 3133

Difficulty: 🟡 Medium
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to construct a strictly increasing array nums of length n such that the bitwise AND of all elements equals x.

Among all valid arrays, we want to minimize the last element, nums[n - 1].

The constraints are important:

  • Every element must be a positive integer.
  • The array must be strictly increasing.
  • The bitwise AND of all elements must equal exactly x.

The most important observation is that if the AND of all numbers is x, then every bit that is set in x must also be set in every element of the array. Otherwise, that bit would disappear from the final AND result.

For example:

  • If x = 100₂ (which is 4), then every number in the array must contain that bit.
  • We are allowed to add extra 1 bits in some positions, because AND only preserves bits that are 1 in every number.

The goal is to make the sequence increasing while keeping the numbers as small as possible.

The constraints go up to 10^8, which means brute force generation of many candidate numbers can become infeasible. We need a solution based on direct bit manipulation rather than simulation.

There are several important edge cases:

  • When n = 1, the answer is simply x, because a single-element array already satisfies the AND condition.
  • When x already has many bits set, there may be very few low positions available for modification.
  • Large values of n may require using higher unused bits to encode distinct increasing values.
  • We must ensure we never unset any bit that exists in x.

Approaches

Brute Force Approach

A straightforward idea is to start from x and search for numbers greater than the previous element that still preserve the overall AND equal to x.

For each candidate number:

  • It must contain all 1 bits from x.
  • We append it to the array if it is larger than the previous value.

We continue until the array reaches size n.

This works because any number that preserves all bits of x can participate in an AND result of x.

However, this approach is too slow. If x is small and n is large, we may need to scan many integers to find valid candidates. In the worst case, the search space becomes enormous.

Key Insight

The crucial observation is that the valid numbers are exactly those formed by:

  • Keeping every 1 bit of x
  • Freely choosing values for positions where x has 0 bits

Those zero-bit positions act like "slots" where we can encode increasing numbers.

Instead of generating candidates one by one, we can directly construct the smallest possible final number.

Think of the sequence as:

  • nums[0] = x
  • The remaining numbers are formed by filling the zero-bit positions of x using binary representations of increasing integers.

The minimum possible last element corresponds to encoding n - 1 into the zero-bit positions of x.

This gives a direct bit manipulation solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(answer) O(1) Scans candidate numbers until enough valid values are found
Optimal O(log n + log x) O(1) Directly maps bits of n - 1 into zero positions of x

Algorithm Walkthrough

Step 1: Convert the problem into bit placement

Every number in the array must preserve all 1 bits of x.

That means:

  • Bits that are 1 in x are fixed
  • Bits that are 0 in x may vary

These variable positions are where we encode increasing values.

Step 2: Observe the ordering pattern

The smallest valid number is simply x.

The next valid numbers are obtained by turning on combinations of zero-bit positions.

For example, if:

x = 100₂

The zero positions are:

bit 0, bit 1, bit 3, bit 4, ...

We can map integers into these positions:

Encoded Value Result
0 100₂ = 4
1 101₂ = 5
2 110₂ = 6
3 111₂ = 7

So the sequence naturally becomes increasing.

Step 3: Use n - 1

Since the first number corresponds to encoded value 0, the final element corresponds to encoded value:

n - 1

We therefore need to insert the binary bits of n - 1 into the zero-bit positions of x.

Step 4: Iterate through bit positions

We scan bit positions from low to high.

For each bit:

  • If the bit in x is 1, we skip it because it is fixed.
  • If the bit in x is 0, we take the next bit from n - 1.

If that bit from n - 1 is 1, we set this position in the answer.

Then we move to the next bit of n - 1.

Step 5: Return the constructed number

After all bits of n - 1 are consumed, the constructed value is the minimum possible final element.

Why it works

The algorithm works because every valid number must contain all 1 bits from x. The remaining positions are independent and can encode arbitrary binary values.

By placing the bits of n - 1 into the lowest available zero positions, we generate the smallest possible number that is the (n - 1)-th valid increasing value after x.

This guarantees:

  • The array can contain n strictly increasing values
  • Every number preserves the AND equal to x
  • The final element is minimized

Python Solution

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        
        result = x
        bit_position = 0
        
        while n > 0:
            # Only use positions where x has a 0 bit
            if ((x >> bit_position) & 1) == 0:
                # Take the next bit from n
                if n & 1:
                    result |= (1 << bit_position)
                
                n >>= 1
            
            bit_position += 1
        
        return result

The implementation starts by converting n into n - 1, because the first valid number corresponds to encoded value 0.

result begins as x, since every valid number must preserve all set bits of x.

We then iterate through bit positions from least significant to most significant.

Whenever we encounter a zero-bit position in x, we use it as an available slot for encoding bits from n - 1.

If the current bit of n - 1 is 1, we set that bit in result.

After processing a slot, we shift n right to consume the used bit.

At the end, result contains the minimum possible final array element.

Go Solution

func minEnd(n int, x int) int64 {
	n--

	result := int64(x)
	bitPosition := 0

	for n > 0 {
		// Use only positions where x has a 0 bit
		if ((x >> bitPosition) & 1) == 0 {
			// Insert next bit from n
			if (n & 1) == 1 {
				result |= (1 << bitPosition)
			}

			n >>= 1
		}

		bitPosition++
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

One important detail is the use of int64 for the result. The final number can exceed the range of a standard 32-bit integer because we may need to place bits into high positions. Using int64 guarantees safe handling of all cases.

Worked Examples

Example 1

Input:
n = 3
x = 4

Binary form:

x = 100₂
n - 1 = 2 = 10₂

We insert bits of 10₂ into zero positions of 100₂.

Bit Position x Bit Next Bit from n-1 Result
0 0 0 100₂
1 0 1 110₂

Final result:

110₂ = 6

Answer:

6

Possible array:

[4, 5, 6]

Example 2

Input:
n = 2
x = 7

Binary form:

x = 111₂
n - 1 = 1 = 1₂

The first available zero bit is at position 3.

Bit Position x Bit Next Bit from n-1 Result
0 1 skip 111₂
1 1 skip 111₂
2 1 skip 111₂
3 0 1 1111₂

Final result:

1111₂ = 15

Answer:

15

Possible array:

[7, 15]

Complexity Analysis

Measure Complexity Explanation
Time O(log n + log x) We scan enough bit positions to process all bits of n and x
Space O(1) Only a few variables are used

The algorithm is extremely efficient because it avoids generating intermediate numbers. Instead, it directly constructs the answer using bit operations.

The number of iterations is bounded by the number of relevant bit positions, which is at most around 60 for typical integer sizes.

Test Cases

solution = Solution()

assert solution.minEnd(3, 4) == 6      # Provided example
assert solution.minEnd(2, 7) == 15     # Provided example

assert solution.minEnd(1, 5) == 5      # Single element array
assert solution.minEnd(1, 1) == 1      # Smallest possible values

assert solution.minEnd(2, 1) == 3      # First zero bit used
assert solution.minEnd(3, 1) == 5      # Multiple encodings

assert solution.minEnd(4, 2) == 7      # Mixed zero and one bits
assert solution.minEnd(5, 8) == 12     # Higher bit positions

assert solution.minEnd(10, 3) == 39    # Larger n with dense bits
assert solution.minEnd(100000000, 1) > 0  # Stress test

assert solution.minEnd(6, 4) == 13     # Multiple zero slots used
assert solution.minEnd(8, 0b1010) == 31  # Alternating bits
Test Why
n=3, x=4 Validates the first sample
n=2, x=7 Validates handling of consecutive set bits
n=1, x=5 Tests single-element edge case
n=2, x=1 Tests smallest expandable value
n=4, x=2 Tests mixed binary structure
n=5, x=8 Tests higher-bit placement
n=10, x=3 Tests many inserted bits
n=100000000, x=1 Stress test for performance
n=6, x=4 Tests multiple available positions
n=8, x=1010₂ Tests alternating bit pattern

Edge Cases

Edge Case 1: n = 1

If the array contains only one element, then the AND of the array is simply that element itself.

So the minimum valid array is:

[x]

and the answer is exactly x.

The implementation handles this naturally because n - 1 becomes 0, so the loop never executes and result remains equal to x.

Edge Case 2: x Has Many Consecutive Set Bits

Consider:

x = 111111₂

There are no available low-bit positions for encoding additional values.

The algorithm correctly skips all occupied positions and eventually uses higher unused bits.

For example:

x = 7 = 111₂
n = 2

The next available position is bit 3, producing:

1111₂ = 15

Edge Case 3: Large n

Large values of n require many encoding bits.

A naive solution might attempt to generate all intermediate numbers, which becomes prohibitively slow.

The optimal solution never generates the sequence explicitly. Instead, it directly maps the binary representation of n - 1 into available bit positions.

This guarantees excellent performance even near the maximum constraints.

Edge Case 4: Sparse Bit Structure in x

Suppose:

x = 100000₂

There are many available low-bit positions.

The algorithm efficiently fills these positions from lowest to highest, guaranteeing the smallest possible final value.

Using lower positions first is essential because lower bits contribute less to the numeric value.