Minimum Array End
MedPrompt
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 <= 108
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of finding the n-th valid number. It starts with x, which is the first valid number, and then iteratively searches for the next strictly larger valid numbers one by one. A number y is considered "valid" if all bits set in x are also set in y, which is equivalent to the condition (y & x) == x. The simulation continues until the n-th valid number is found.
Algorithm
- Initialize a variable
current_numtox. This represents the first and smallest valid number. - Loop
n-1times to find the subsequentn-1valid numbers. - In each iteration, increment
current_numto find the next potential candidate. - Start an inner loop that continues as long as
current_numis not a valid number. A numberyis valid if(y & x) == x. - Inside the inner loop, keep incrementing
current_numuntil the validity condition is met. - After the outer loop completes,
current_numwill hold the value of then-th valid number. - Return
current_num.
Walkthrough
The algorithm begins by recognizing that x is the smallest positive integer whose bitwise AND with itself is x. Thus, x is the first element in our sequence of valid numbers. To find the n-th element, we need to find n-1 more valid numbers, each strictly greater than the previous one.
We can implement this by starting with a variable current_num set to x. We then enter a loop that runs n-1 times. In each iteration, we search for the next valid number. We do this by incrementing current_num and then checking if it satisfies the condition (current_num & x) == x. If it doesn't, we continue incrementing current_num until the condition is met. This process guarantees that we find the smallest valid number that is greater than the previously found one. After n-1 iterations, current_num will hold the n-th valid number, which is the minimum possible value for the last element of the array.
class Solution { public long minArrayEnd(int n, int x) { long current_num = x; // We need to find n-1 more valid numbers after the first one (x). for (int i = 1; i < n; i++) { current_num++; // Keep incrementing until we find the next number y such that (y & x) == x. while ((current_num & x) != x) { current_num++; } } return current_num; }}Complexity
Time
O(Y_n - x) where Y_n is the final answer. The gap between consecutive valid numbers can be very large. For instance, if `x = 2^k - 1`, the next valid number is `x + 2^k`. With `n` up to `10^8`, the total number of increments can be huge, making this approach too slow.
Space
O(1) - The algorithm uses a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Directly models the problem statement without complex logic.
Cons
Extremely inefficient and will result in a Time Limit Exceeded (TLE) error for the given constraints.
The runtime depends on the magnitude of the final answer, not just the input size
n.
This highly efficient approach leverages bitwise operations to construct the answer directly. It's based on the observation that any number y satisfying y & x = x must have all of x's set bits also set. This means y can be formed by taking x and setting some additional bits that are 0 in x (let's call these "free bits"). The problem then transforms into finding the n-th smallest number that can be formed this way. This corresponds to finding the (n-1)-th number that can be formed using only the free bits, and adding it to x.
Algorithm
- The core insight is that any valid number
ymust be of the formx | kwherek & x = 0. This is equivalent toy = x + k. - To find the
n-th smallest valid number, we need to find then-th smallest non-negative integerksuch thatk & x = 0. - The
n-th suchk(forn >= 1) can be constructed by using the bits of the numberm = n - 1. - The bits of
mare mapped to the "free" bit positions ofx(positions wherexhas a0bit). - Let
m = n - 1. Initializeresult = x. - Iterate while
m > 0:- Find the next available free bit position,
bit_pos, where the bit ofxis0. - If the least significant bit of
mis1, set thebit_pos-th bit in theresult. - Right-shift
mto process its next bit and incrementbit_posto find the next free slot.
- Find the next available free bit position,
- Return the final
result.
Walkthrough
A number y is valid if and only if y & x = x. This implies that for every bit set in x, the corresponding bit must also be set in y. The other bits of y (where x has 0s) can be either 0 or 1. This means any valid number y can be expressed as y = x | k, where k is a number whose set bits are only at positions where x has 0s (i.e., k & x = 0).
To find the n-th smallest valid number, we need to find the n-th smallest non-negative k satisfying k & x = 0 and add it to x. The sequence of such k values in increasing order corresponds to taking the integers 0, 1, 2, 3, ... and mapping their bits to the free bit positions of x.
Specifically, the n-th smallest valid number is constructed using the bits of n-1. Let m = n-1. We iterate through the bits of m. If the i-th bit of m is 1, we find the i-th free bit position in x (0-indexed) and set that bit. The final result is x plus all these added bits.
class Solution { public long minArrayEnd(int n, int x) { // We need to find the n-th number in the sequence of valid numbers. // A valid number 'y' must satisfy (y & x) == x. // This means y can be written as x | k, where (k & x) == 0. // The n-th smallest valid number corresponds to the n-th smallest k. // The n-th smallest k (for n>=1) is constructed from the bits of (n-1). long m = n - 1; long result = (long)x; // Start with x, and add bits to it. int bit_pos = 0; while (m > 0) { // Find the next bit position that is NOT set in x. // This is a "free" bit we can use. while (((x >> bit_pos) & 1) == 1) { bit_pos++; } // If the current LSB of m is 1, we set the corresponding free bit in our result. if ((m & 1) == 1) { result |= (1L << bit_pos); } // Move to the next bit of m and the next bit position for the next free slot. m >>= 1; bit_pos++; } return result; }}Complexity
Time
O(log n + log x) - The main loop runs `O(log n)` times (for each bit in `n-1`). Inside the loop, we search for the next free bit. The bit position counter `bit_pos` only increases. Its final value is bounded by the number of bits in `n-1` plus the number of bits in `x`, which is `O(log n + log x)`. This is very fast.
Space
O(1) - The algorithm uses only a few variables, requiring constant extra space.
Trade-offs
Pros
Extremely efficient and optimal for the given constraints.
Calculates the result directly without iteration over non-valid numbers.
Constant time complexity with respect to the magnitude of
nandx, depending only on their number of bits.
Cons
The logic is less intuitive compared to a direct simulation.
Requires a good understanding of bitwise operations.
Solutions
Solution
class Solution {public long minEnd(int n, int x) { --n; long ans = x; for (int i = 0; i < 31; ++i) { if ((x >> i & 1) == 0) { ans |= (n & 1) << i; n >>= 1; } } ans |= (long)n << 31; return ans; }}class Solution: def minEnd(self, n: int, x: int) -> int: n -= 1 ans = x for i in range(31): if x >> i & 1 ^ 1: ans |= (n & 1) << i n >>= 1 ans |= n << 31 return ansclass Solution {public: long long minEnd(int n, int x) { --n; long long ans = x; for (int i = 0; i < 31; ++i) { if (x >> i & 1 ^ 1) { ans |= (n & 1) << i; n >>= 1; } } ans |= (1LL * n) << 31; return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.