Construct the Minimum Bitwise Array II - Video Solutions
Construct the Minimum Bitwise Array I & II | LeetCode 3314 & 3315 | Brute & Optimal Solution
Construct the Minimum Bitwise Array II - Video Solution
Watch 10 video solutions for Construct the Minimum Bitwise Array II, a medium level problem involving Array, Bit Manipulation. This walkthrough by Sanyam IIT Guwahati has 1,875 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- For
i = 0, as there is no value forans[0]that satisfiesans[0] OR (ans[0] + 1) = 2, soans[0] = -1. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 3is1, because1 OR (1 + 1) = 3. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 5is4, because4 OR (4 + 1) = 5. - For
i = 3, the smallestans[3]that satisfiesans[3] OR (ans[3] + 1) = 7is3, because3 OR (3 + 1) = 7.
Example 2:
Input: nums = [11,13,31]
Output: [9,12,15]
Explanation:
- For
i = 0, the smallestans[0]that satisfiesans[0] OR (ans[0] + 1) = 11is9, because9 OR (9 + 1) = 11. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 13is12, because12 OR (12 + 1) = 13. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 31is15, because15 OR (15 + 1) = 31.
Constraints:
1 <= nums.length <= 1002 <= nums[i] <= 109nums[i]is a prime number.
Approach Overview
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.
Complexity Analysis
| 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 |