Construct the Minimum Bitwise Array II
MedPrompt
You are given an array nums consisting of n prime integers.
You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i].
Additionally, you must minimize each value of ans[i] in the resulting array.
If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1.
Example 1:
Input: nums = [2,3,5,7]
Output: [-1,1,4,3]
Explanation:
- For
i = 0, as there is no value forans[0]that satisfiesans[0] OR (ans[0] + 1) = 2, soans[0] = -1. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 3is1, because1 OR (1 + 1) = 3. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 5is4, because4 OR (4 + 1) = 5. - For
i = 3, the smallestans[3]that satisfiesans[3] OR (ans[3] + 1) = 7is3, because3 OR (3 + 1) = 7.
Example 2:
Input: nums = [11,13,31]
Output: [9,12,15]
Explanation:
- For
i = 0, the smallestans[0]that satisfiesans[0] OR (ans[0] + 1) = 11is9, because9 OR (9 + 1) = 11. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 13is12, because12 OR (12 + 1) = 13. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 31is15, because15 OR (15 + 1) = 31.
Constraints:
1 <= nums.length <= 1002 <= nums[i] <= 109nums[i]is a prime number.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves a straightforward search for the solution. For each number nums[i] in the input array, we iterate through all possible candidate values for ans[i] starting from 0. The first value that satisfies the condition ans[i] OR (ans[i] + 1) == nums[i] is guaranteed to be the minimum possible value. If no such value is found up to nums[i] - 1, we conclude that no solution exists.
Algorithm
- Initialize an answer array
ansof the same size asnums. - For each element
numat indexiinnums:- Set a flag
found = false. - Iterate with a variable
xfrom0up tonum - 1. The smallest solutionxmust satisfyx | (x+1) >= x+1, sonum >= x+1, which impliesx <= num - 1. - In each iteration, check if
x | (x + 1) == num. - If the condition is true, we have found the smallest
x. Setans[i] = x, setfound = true, and break the inner loop. - After the loop, if
foundis stillfalse, it means no solution exists. Setans[i] = -1.
- Set a flag
- Return the
ansarray.
Walkthrough
The algorithm iterates through each number in the nums array. For each number, say num, it starts a search for a corresponding ans value, let's call it x. The search for x begins at 0 and goes up to num - 1. We know the solution x cannot be greater than or equal to num because x | (x+1) would be at least num+1. For each x, it checks if x | (x + 1) equals num. Since we are iterating x in increasing order, the first x that satisfies this condition is the minimum solution. If the loop finishes without finding a solution, we set the answer to -1.
class Solution { public int[] constructArray(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { int num = nums[i]; int result = -1; // The smallest solution x must be less than num because x | (x+1) >= x+1. // So, num >= x+1, which means x <= num - 1. for (int x = 0; x < num; x++) { if ((x | (x + 1)) == num) { result = x; break; } } ans[i] = result; } return ans; }}Complexity
Time
O(N * M), where N is the length of `nums` and M is the maximum value in `nums`. Given M can be up to 10^9, this approach is not feasible.
Space
O(N) for the output array. If the output array is not considered, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Correctly finds the minimum solution if one exists within the time limits.
Cons
Extremely inefficient due to the nested loop structure.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints, as
nums[i]can be up to 10^9.
A highly efficient approach can be developed by analyzing the bitwise properties of the expression x | (x + 1) and how it relates to y = nums[i]. By considering the parity of x and the last two bits of y (i.e., y % 4), we can establish a set of rules that directly compute the smallest x without any iteration or searching.
Algorithm
- Initialize an answer array
ans. - Iterate through each
numat indexiinnums:- If
num == 2, setans[i] = -1. - If
num % 4 == 1, the solution must be even. Setans[i] = num - 1. - If
num % 4 == 3:- Check if
numis a Mersenne prime (a prime of the form2^k - 1). This can be checked with the bitwise trick((long)num + 1 & num) == 0. - If it is a Mersenne prime, the smallest solution is
ans[i] = (num - 1) / 2. - Otherwise, the smallest solution is
ans[i] = num - 2.
- Check if
- If
- Return the
ansarray.
Walkthrough
This optimal solution is based on a case-by-case analysis of the input number num.
-
Case
num = 2:2is the only even prime. It can be shown that no integerxsatisfiesx | (x+1) = 2. So, the answer is -1. -
Case
numis an odd prime: We analyze based on the last two bits ofnum.- If
num % 4 == 1(binary ends in...01): Forx | (x+1)to have a 0 at the second-to-last bit,xmust be an even number. For an evenx,x | (x+1)simplifies tox+1. Thus,x+1 = num, which givesx = num - 1. This is the only possible solution, and therefore the minimum. - If
num % 4 == 3(binary ends in...11): In this case,xcould be even or odd. The even solution isx_even = num - 1. We must also find the smallest odd solutionx_oddand compare.- If
numis a Mersenne prime (a prime of the form2^k - 1, like 3, 7, 31), the smallest odd solution isx_odd = (num - 1) / 2. This is always smaller thanx_even. - If
numis not a Mersenne prime (like 11, 19, 23), the smallest odd solution isx_odd = num - 2. This is also smaller thanx_even.
- If
- If
This logic allows for a constant-time calculation for each number.
class Solution { public int[] constructArray(int[] nums) { int n = nums.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { int num = nums[i]; if (num == 2) { ans[i] = -1; } else if (num % 4 == 1) { ans[i] = num - 1; } else { // num % 4 == 3 // Check if num is a Mersenne prime (of the form 2^k - 1) // A number n is of the form 2^k-1 iff (n+1) & n == 0 if (((long)num + 1 & num) == 0) { ans[i] = (num - 1) / 2; } else { ans[i] = num - 2; } } } return ans; }}Complexity
Time
O(N), where N is the length of `nums`. Each number in the input array is processed in constant time.
Space
O(N) for the output array. The auxiliary space complexity is O(1).
Trade-offs
Pros
Extremely efficient, with an optimal time complexity.
Directly computes the answer using arithmetic and bitwise operations, avoiding any loops or searches for each number.
Cons
The logic is non-trivial and requires careful mathematical and bitwise reasoning to derive and prove correctness.
Solutions
Solution
class Solution {public int[] minBitwiseArray(List<Integer> nums) { int n = nums.size(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int x = nums.get(i); if (x == 2) { ans[i] = -1; } else { for (int j = 1; j < 32; ++j) { if ((x >> j & 1) == 0) { ans[i] = x ^ 1 << (j - 1); break; } } } } return ans; }}class Solution {public: vector<int> minBitwiseArray(vector<int> &nums) { vector<int> ans; for (int x : nums) { if (x == 2) { ans.push_back(-1); } else { for (int i = 1; i < 32; ++i) { if (x >> i & 1 ^ 1) { ans.push_back(x ^ 1 << (i - 1)); break; } } } } return ans; }};class Solution: def minBitwiseArray(self, nums: List[int]) -> List[int]: ans = [] for x in nums: if x == 2: ans . append(- 1) else: for i in range(1, 32): if x >> i & 1 ^ 1: ans . append(x ^ 1 << (i - 1)) break return ansVideo 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.