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.Problem Overview: You receive an integer array nums. For each value, construct the smallest possible integer ans[i] such that ans[i] | (ans[i] + 1) == nums[i]. If no such value exists, return -1 for that position. The task mainly tests understanding of bit manipulation patterns that appear when OR is applied to consecutive integers.
Approach 1: Iterative Check for OR Condition (O(n * v) time, O(1) space)
The most direct method is brute force. For each value in the array, iterate candidate values x starting from 0 up to nums[i]. For each candidate, compute x | (x + 1). The first value that produces nums[i] is the minimum valid answer. If no candidate satisfies the condition, store -1. This approach works because the search space is bounded by the value itself and guarantees the smallest valid x. However, it performs repeated OR computations and becomes inefficient when numbers are large.
Approach 2: Bit Manipulation to Find Minimum ans[i] (O(n) time, O(1) space)
A key observation simplifies the problem. When two consecutive numbers x and x+1 are OR-ed, the result becomes a number whose least significant bits are all 1 up to the first zero bit in x. Because of this property, the result must always be odd. If nums[i] is even, no valid x exists and the answer is -1.
For odd values, count the number of trailing 1 bits in nums[i]. Flipping the second-to-last trailing 1 gives the smallest x that reconstructs the number when OR-ed with its successor. In practice, this can be computed using simple bit operations such as XOR with a power of two derived from the trailing-one count. This removes the need for iteration and processes each element in constant time.
This pattern appears frequently in bit manipulation interview problems where relationships between consecutive integers reveal predictable bit transitions. Recognizing the trailing-ones structure allows you to derive the answer directly.
Recommended for interviews: Start by describing the brute-force search to demonstrate understanding of the OR condition. Then move to the bit-pattern insight that consecutive integers propagate trailing ones. Interviewers expect the optimized O(n) solution because it shows comfort with binary reasoning and low-level bit operations.
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.
Python
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.
Time Complexity: O(1000 * n) where 1000 iterations max for each number.
Space Complexity: O(n) for storing the answer.
For an integer a, the result of a \lor (a + 1) is always odd. Therefore, if nums[i] is even, then ans[i] does not exist, and we directly return -1. In this problem, nums[i] is a prime number, so to check if it is even, we only need to check if it equals 2.
If nums[i] is odd, suppose nums[i] = 0b1101101. Since a \lor (a + 1) = nums[i], this is equivalent to changing the last 0 bit of a to 1. To solve for a, we need to change the bit after the last 0 in nums[i] to 0. We start traversing from the least significant bit (index 1) and find the first 0 bit. If it is at position i, we change the (i - 1)-th bit of nums[i] to 1, i.e., ans[i] = nums[i] \oplus 2^{i - 1}.
By traversing all elements in nums, we can obtain the answer.
The time complexity is O(n times log M), where n and M are the length of the array nums and the maximum value in the array, respectively. Ignoring the space consumption of the answer array, the space complexity is O(1).
| 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. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Check for OR Condition | O(n * v) | O(1) | Good for understanding the definition or when values are very small |
| Bit Manipulation Using Trailing Ones | O(n) | O(1) | Optimal approach for interviews and large inputs |
Construct the Minimum Bitwise Array I & II | Brute Force | Optimal | Leetcode 3314 & 3315 | MIK • codestorywithMIK • 15,728 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