#3315

Medium

LeetCode Problem Workspace

Construct the Minimum Bitwise Array II

Learn to build the minimum array matching a bitwise OR pattern for each prime in nums, focusing on binary optimization.

Problem Statement

You are given an array nums of length n containing prime integers. Your goal is to construct an array ans of the same length where each element satisfies a specific bitwise property.

For each index i, the condition ans[i] OR (ans[i] + 1) must equal nums[i]. Additionally, ans[i] should be minimized for all i. You must return the completed array that satisfies these constraints.

Examples

Example 1

Input: nums = [2,3,5,7]

Output: [-1,1,4,3]

Example 2

Input: nums = [11,13,31]

Output: [9,12,15]

Constraints

1 <= nums.length <= 100
2 <= nums[i] <= 109
nums[i] is a prime number.

Solution Approach

Analyze Binary Patterns

Convert each nums[i] to binary and observe positions of 1s and 0s. Focus on the rightmost zeros to determine the minimal ans[i] value that meets ans[i] OR (ans[i]+1) == nums[i].

Greedy Construction

Iterate through nums, setting ans[i] to the largest number less than nums[i] with zeros where nums[i] has ones. This ensures the OR with ans[i]+1 reaches nums[i] while keeping values minimal.

Validation and Edge Cases

Check that all generated ans[i] values satisfy the OR condition. Handle edge cases where nums[i] is small or where a minimal solution may involve negative numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating through each nums[i] and computing binary manipulations, roughly O(n * log(nums[i])). Space complexity is O(n) for storing the resulting ans array.

What Interviewers Usually Probe

Focus on bitwise OR patterns rather than arithmetic approaches.
Consider how minimizing each ans[i] might conflict with satisfying the OR condition.
Expect questions on handling edge cases when nums[i] has consecutive ones in binary.

Common Pitfalls or Variants

Common pitfalls

Assuming ans[i] can be nums[i]-1 without verifying the OR condition.
Ignoring binary representation patterns that affect minimal solutions.
Failing to handle small prime values or negative minimal results correctly.

Follow-up variants

Construct the minimum array for bitwise AND instead of OR.
Allow composite numbers instead of only prime numbers in nums.
Find ans array maximizing values instead of minimizing while satisfying OR.

FAQ

What does 'Construct the Minimum Bitwise Array II' mean in practice?

It means generating an array where each element OR its increment equals the corresponding nums[i], while keeping values as small as possible.

Can ans[i] be negative?

Yes, in some cases minimizing ans[i] to satisfy the OR condition may produce negative values for small nums[i].

Is there a direct formula for ans[i]?

No universal formula exists; each ans[i] depends on the binary pattern of nums[i] and requires bitwise analysis.

What is the role of binary representation in this problem?

Binary representation shows which bits must be set or unset, guiding the minimal construction of ans[i] for the OR condition.

Can this approach be applied to arrays with non-prime numbers?

Yes, but the pattern of minimal ans[i] values may differ and require careful handling of bitwise constraints.

terminal

Solution

Solution 1: Bit Manipulation

For an integer $a$, the result of $a \lor (a + 1)$ is always odd. Therefore, if $\text{nums[i]}$ is even, then $\text{ans}[i]$ does not exist, and we directly return $-1$. In this problem, $\textit{nums}[i]$ is a prime number, so to check if it is even, we only need to check if it equals $2$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        ans = []
        for x in nums:
            if x == 2:
                ans.append(-1)
            else:
                for i in range(1, 32):
                    if x >> i & 1 ^ 1:
                        ans.append(x ^ 1 << (i - 1))
                        break
        return ans

Continue Practicing

#3314 construct the minimum bitwise array i #3309 maximum possible number by binary concatenation #3287 find the maximum sequence value of array