Minimum Array End
The key idea
Every element must keep all of
x's set bits, so the bits where x is 1 are locked. The remaining 0 positions of x are free, and the n distinct values map exactly to 0, 1, 2, ..., n-1 written into those free bits. The largest value uses n-1, so spread the bits of n-1 into x's zero slots from low to high.Problem
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].
Constraints
1 <= n, x <= 10^8
Examples
Input: n = 3, x = 4
Output: 6
Input: n = 2, x = 7
Output: 15
Input: n = 4, x = 5
Output: 15
Complexity
Time: O(log n + log x) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization