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 <= 108In #3133 Minimum Array End, we need to construct an increasing array of size n such that the bitwise AND of all elements equals x, while minimizing the final element. The key observation is that every number in the array must keep all the set bits of x; otherwise the final AND would drop below x. Therefore, the variability between elements can only come from positions where x has zero bits.
A useful strategy is to think of generating the next valid numbers by distributing the binary representation of n - 1 across the zero-bit positions of x. This effectively simulates how the sequence grows while preserving the required AND value. By filling these available bit positions from least significant to most significant, we can compute the smallest possible value for the final element.
This approach relies on bit manipulation and processes only the bits of the numbers involved, making it highly efficient. The solution runs in O(log n) time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Bit Manipulation (filling zero-bit positions of x) | O(log n) | O(1) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Each element of the array should be obtained by “merging” <code>x</code> and <code>v</code> where <code>v = 0, 1, 2, …(n - 1)</code>.
To merge <code>x</code> with another number <code>v</code>, keep the set bits of <code>x</code> untouched, for all the other bits, fill the set bits of <code>v</code> from right to left in order one by one.
So the final answer is the “merge” of <code>x</code> and <code>n - 1</code>.
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.
Time Complexity: O(1)
Space Complexity: O(1)
1def minimum_array_end(n, x):
2 return x + n - 1
3
4n = 3
5x = 4
6printThe Python implementation follows a straightforward approach where the final minimal number is calculated by adding n-1 to x.
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.
Time Complexity: O(n)
Space Complexity: O(1)
using namespace std;
int minimumArrayEnd(int n, int x) {
int high_possible_val = x;
for (int i = 1; i < n; i++) {
high_possible_val |= (1 << i);
}
return high_possible_val;
}
int main() {
int n = 3, x = 4;
cout << minimumArrayEnd(n, x) << endl;
return 0;
}Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Since the first element effectively starts from x, we only need to simulate the remaining n-1 increments. Mapping the bits of n-1 into the zero-bit positions of x gives the minimal valid value for the final element.
Problems involving bit manipulation and greedy construction like Minimum Array End are common in technical interviews at FAANG-style companies. They test understanding of binary representation, optimization, and low-level reasoning.
No complex data structure is required. The problem can be solved using simple bitwise operations and integer variables, making it efficient in both time and memory.
The optimal approach uses bit manipulation. The idea is to preserve all set bits of x and use the zero-bit positions to encode the binary representation of n-1, which determines how the array grows while keeping the bitwise AND equal to x.
Similarly, in C++, bitwise OR is used strategically on the initial value to tweak high order bits to get values that satisfy unique conditions for keeping a bitwise AND result of x optimized.