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 = 4
Output: 6
Explanation:
nums can be [4,5,6] and its last element is 6.
Example 2:
Input: n = 2, x = 7
Output: 15
Explanation:
nums can be [7,15] and its last element is 15.
Constraints:
1 <= n, x <= 108Problem Overview: You need to build an increasing array of size n where the bitwise AND of all elements equals x. The goal is to keep the array valid while making the last element as small as possible.
Approach 1: Incremental Construction (O(n) time, O(1) space)
Start the array with arr[0] = x. For every next element, increment the previous value until the condition (value & x) == x holds. This guarantees every number keeps all bits that appear in x, so the AND of the entire array never drops below x. In practice you compute the next value using next = (prev + 1) | x, which forces required bits back to 1. Repeat this process n-1 times until the array reaches size n. The approach is simple and intuitive because it directly simulates building the array while maintaining the constraint. Time complexity is O(n) since each step computes the next valid value, and space complexity is O(1). This approach relies heavily on operations from bit manipulation.
Approach 2: Binary Manipulation (O(log n) time, O(1) space)
The key observation is that every element must contain all the set bits of x. The only freedom comes from the bit positions where x has 0. Instead of constructing the array explicitly, encode the sequence growth directly into those zero-bit positions. Let k = n - 1. Traverse the bits of x from least significant to most significant. Whenever a bit in x is 0, take the next bit from k and place it into that position. If the bit in x is already 1, keep it unchanged. This effectively distributes the binary representation of n-1 across the available zero positions of x, producing the smallest possible final number while maintaining the AND constraint. The algorithm runs in O(log n) time because you process each bit once, and uses O(1) extra space. This technique is a classic pattern in bit manipulation and bitmask problems where unused bit positions encode additional state.
Recommended for interviews: The binary manipulation approach is what most interviewers expect. It shows you understand how bit constraints propagate across numbers and how to encode sequence indices inside unused bits. The incremental construction method still helps demonstrate the underlying rule ((value & x) == x), but the optimized bit mapping solution proves stronger problem-solving skills.
In this approach, we begin by constructing an array where each element is initialized to the given value of x. We then increment each subsequent element by 1 ensuring that it is greater than the previous element. We stop when we've constructed an array of size n.
This works because the bitwise AND of all numbers will still be x, since all elements are derived from x and only the last element needs to change significantly to ensure uniqueness and satisfy the increasing property.
The function calculates the minimum possible value of the last element by starting with x and incrementing it by n - 1 to ensure all previous n-1 elements are strictly increasing starting from x.
Time Complexity: O(1)
Space Complexity: O(1)
In this approach, we consider constructing the array by leveraging the bitwise properties to ensure the AND operation returns x. We create the first n-1 elements as numbers starting from x incrementally, and ensure the last element is the smallest number fitting the need for bitwise AND to be x.
To optimize the last number's structure, we can explore modifying bits in consideration of the upcoming elements and control zeroed bits strategically to adjust value and ensure valid returns upon AND calculation.
This C code uses bit manipulation to construct the minimum end element. By setting the suitable bits, we obtain potential n-1 lower bits set to create a higher value that preserves higher x values, exploiting AND product properties.
Time Complexity: O(n)
Space Complexity: O(1)
According to the problem description, to make the last element of the array as small as possible and the bitwise AND result of the elements in the array is x, the first element of the array must be x.
Assume the binary representation of x is \underline{1}00\underline{1}00, then the array sequence is \underline{1}00\underline{1}00, \underline{1}00\underline{1}01, \underline{1}00\underline{1}10, \underline{1}00\underline{1}11...
If we ignore the underlined part, then the array sequence is 0000, 0001, 0010, 0011..., the first item is 0, then the n-th item is n-1.
Therefore, the answer is to fill each bit of the binary of n-1 into the 0 bit of the binary of x based on x.
The time complexity is O(log x), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Incremental Construction | Time Complexity: O(1) |
| Approach 2: Binary Manipulation | Time Complexity: O(n) |
| Greedy + Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Incremental Construction | O(n) | O(1) | Good for understanding the constraint and simulating the array step by step |
| Binary Manipulation | O(log n) | O(1) | Best for large n and interviews; computes the final value directly |
Minimum Array End - Leetcode 3133 - Python • NeetCodeIO • 13,573 views views
Watch 9 more video solutions →Practice Minimum Array End with our built-in code editor and test cases.
Practice on FleetCode