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] <= 1000nums[i] is a prime number.To solve the problem, note that for any number x, the result of x OR (x + 1) will be a number that has all the bits of x, plus at least one more.
Thus, for any prime number p, the smallest number x for which x OR (x + 1) = p happens to be when we can have x such that it contains all bits of p-1.
Thus, iterate over powers of two combinations that are not part of p's binary representation to find the smallest ans[i].
The logic here is to compute if a number p can be generated using the pattern which primarily requires finding p-1 equivalent truths in forming the OR.
JavaScript
C++
Time Complexity: O(1) for checking a bitwise condition.
Space Complexity: O(n) for storing the answer.
Instead of computing directly using bit manipulation, this approach checks in a brute-force like manner from 0 upwards to verify which x satisfies x OR (x + 1) = p, thus ensuring minimal x.
This solution takes up every number from 0 to ensure that if the direct OR comparison backs to the respected prime number, output is appended.
C
C#
Time Complexity: O(1000 * n) where 1000 iterations max for each number.
Space Complexity: O(n) for storing the answer.
| Approach | Complexity |
|---|---|
| Bit Manipulation to Find Minimum `ans[i]` | Time Complexity: O(1) for checking a bitwise condition. |
| Iterative Check for OR Condition | Time Complexity: O(1000 * n) where 1000 iterations max for each number. |
❌ 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 I with our built-in code editor and test cases.
Practice on FleetCode