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.Problem Overview: You receive an integer array nums. For every value nums[i], construct the smallest integer a such that a | (a + 1) = nums[i]. If no such value exists, return -1. The result is an array where each position contains the minimum valid a for the corresponding number.
Approach 1: Brute Force Search (O(n * m) time, O(1) space)
Try all possible candidates for each element until the condition a | (a + 1) == nums[i] becomes true. Start from a = 0 and increment until the OR result matches the target. The first valid a is the minimum by definition. This approach directly simulates the operation and is useful for understanding how the OR behavior works between consecutive integers. However, the search range can grow large for bigger values of nums[i], making the approach inefficient in practice.
Approach 2: Bit Manipulation Insight (O(n) time, O(1) space)
The expression a | (a + 1) has a predictable binary pattern. When you increment a number, the rightmost block of 1 bits flips to 0 and the first 0 before them becomes 1. Taking the OR with the previous number turns that entire suffix into 1s. As a result, every valid output must end with a sequence of trailing 1 bits.
If nums[i] is even, the least significant bit is 0, which means it cannot be formed by a | (a + 1). In that case return -1. Otherwise count the number of trailing 1s in the binary representation of nums[i]. If that count is k, the smallest valid value of a is nums[i] - 2^(k-1). This works because removing that bit recreates the exact carry behavior that produces the trailing ones when OR-ing with a + 1.
The algorithm simply scans the array once, performs a few bit operations per element, and constructs the answer in linear time. This makes it the optimal solution for large inputs and a classic example of recognizing binary patterns in bit manipulation problems.
Recommended for interviews: Start by describing the brute force search to demonstrate the definition of the condition. Then transition to the binary observation about trailing 1s produced by a | (a + 1). Interviewers expect the optimized bit reasoning approach because it reduces the complexity to O(n) and shows strong understanding of binary behavior. This problem commonly appears in discussions around Bit Manipulation and Array traversal patterns.
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.
Python
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.
Python
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.
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 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 |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | O(n * m) | O(1) | Understanding the definition of a | (a+1) or validating the pattern for small inputs |
| Bit Manipulation (Trailing Ones) | O(n) | O(1) | Optimal approach for large arrays using binary pattern observation |
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 II with our built-in code editor and test cases.
Practice on FleetCode