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 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Incremental Construction | Time Complexity: O(1) |
| Approach 2: Binary Manipulation | Time Complexity: O(n) |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,296 views views
Watch 9 more video solutions →Practice Minimum Array End with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor