Watch 10 video solutions for Construct the Minimum Bitwise Array I, a easy 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] <= 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.
| 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 |