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