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:
i = 0, as there is no value for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1.i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3.i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5.i = 3, the smallest ans[3] that satisfies ans[3] OR (ans[3] + 1) = 7 is 3, because 3 OR (3 + 1) = 7.Example 2:
Input: nums = [11,13,31]
Output: [9,12,15]
Explanation:
i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11.i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13.i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 31 is 15, because 15 OR (15 + 1) = 31.
Constraints:
1 <= nums.length <= 1002 <= nums[i] <= 109nums[i] is a prime number.This approach relies on understanding the binary representation of numbers and utilizing bitwise operations effectively. The challenge is to decompose nums[i] into two consecutive numbers whose OR equals nums[i]. The key lies in setting the least significant zero bit in nums[i] to one. If there is no such zero, it is impossible to achieve and thus the result should be -1.
The algorithm iterates over each element in nums. If num is odd, it itself is a valid answer because odd numbers already meet the condition. For even num, we attempt to find ans[i] by identifying the smallest number y such that y OR (y + 1) = num. This is done by checking if removing the least significant set bit yields a number that still satisfies the condition.
C++
Java
JavaScript
Time Complexity: O(n), where n is the number of elements in the nums array.
Space Complexity: O(1), if we don't consider the output array as additional space.
This is a straightforward method that attempts to find solutions for each element in the nums array by brute-force checking each potential value for ans[i]. This approach is inefficient but guarantees correctness as it checks all possibilities.
This brute-force Python function iterates through each possible value from 0 to num - 1 for each element in nums and checks if it satisfies the condition. Once a valid ans is found, it stops further checks and moves to the next number. If no valid answer is found, it appends -1.
Time Complexity: O(n * m), where n is the size of the nums array and m is the average value in nums.
Space Complexity: O(1), not counting the output array.
| Approach | Complexity |
|---|---|
| Bit Manipulation Approach | Time Complexity: O(n), where n is the number of elements in the |
| Brute-force Approach | Time Complexity: O(n * m), where n is the size of the |
❌ Don't Run Behind 500 LEETCODE Problems ❌ Focus on QPCD • Striver • 522,282 views views
Watch 9 more video solutions →Practice Construct the Minimum Bitwise Array II with our built-in code editor and test cases.
Practice on FleetCode