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.
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; }}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.