Watch 10 video solutions for Construct the Minimum Bitwise Array II, a medium level problem involving Array, Bit Manipulation. This walkthrough by codestorywithMIK has 15,728 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |