LeetCode Problem 3315

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

LeetCode 3315 - Construct the Minimum Bitwise Array II

Problem Understanding

We are given an array nums where every element is a prime number. For each value nums[i], we must find the smallest non-negative integer ans[i] such that:

$$ans[i] ;|; (ans[i] + 1) = nums[i]$$

where | denotes the bitwise OR operation.

If no such value exists, we must place -1 in the answer array at that position.

The important detail is that we are not merely looking for any valid value. Among all values that satisfy the equation, we must choose the minimum possible one.

The input consists of up to 100 prime numbers, and each prime can be as large as $10^9$. The relatively small array size suggests that even an $O(n \log M)$ solution would be easily fast enough, where $M$ is the magnitude of the numbers.

The challenge is understanding the structure of:

$$x ;|; (x+1)$$

and then reversing this operation efficiently.

A few important observations arise immediately.

If nums[i] = 2, there is no solution. The only possible candidates are:

• 0 | 1 = 1
• 1 | 2 = 3

No value produces 2.

Another important observation is that every prime except 2 is odd. Since x | (x+1) is always odd, all odd primes potentially have solutions.

The key task is determining the minimum valid x for a given odd prime.

Approaches

Brute Force

A straightforward approach would be to try every possible value x from 0 upward and check whether:

$$x | (x+1) = nums[i]$$

The first valid value found would be the answer because we are searching in increasing order.

This approach is correct because it exhaustively checks every candidate and eventually finds the minimum valid one if it exists.

However, it is completely impractical. Since nums[i] can be as large as $10^9$, the search space may contain hundreds of millions of candidates.

Key Insight

Consider how adding one changes binary representations.

Suppose x ends with a block of trailing ones:

xxxxx01111

Adding one produces:

xxxxx10000

Now compute the OR:

xxxxx01111
xxxxx10000
-----------
xxxxx11111

The result is obtained by turning the rightmost zero bit of x into 1, while all lower bits remain 1.

Therefore, if:

$$y = x | (x+1)$$

then y must contain a contiguous suffix of ones.

To reverse the process, let y = nums[i].

We want the smallest possible x.

Since:

$$y = x | (x+1)$$

the rightmost zero involved in the transition becomes a one in y.

To minimize x, we want to clear the highest possible bit that can be removed while still allowing the OR operation to reconstruct y.

For an odd number y, find the first zero bit when scanning from the least significant bit upward through the trailing ones. If that zero is at position p, then the bit immediately below it, position p-1, can be cleared to obtain the minimum valid x.

Equivalently:

• Find the first zero bit in y.
• Let its position be p.
• Answer is:

$$y - 2^{p-1}$$

The only exception is y = 2, which has no solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n·M)	O(1)	Tries every candidate value
Optimal	O(n·log M)	O(1)	Uses binary structure of x OR (x+1)

Algorithm Walkthrough

1. Create an empty answer array.
2. Process each prime number num independently.
3. If num == 2, append -1 because no integer x satisfies x | (x + 1) = 2.
4. Otherwise, scan bits from least significant to most significant until finding the first bit position whose value is 0.
5. Suppose that zero bit is found at position p.
6. The minimum valid value is obtained by clearing bit p - 1 from num.
7. Compute:

$$ans = num - 2^{p-1}$$ 8. Append this value to the result array. 9. After processing all elements, return the result.

Why it works

For an odd number, the bits from position 0 through p-1 are all 1, and bit p is the first 0. Any value x satisfying the equation must contain a zero somewhere inside that suffix of ones so that adding one creates the carry chain. To minimize x, we clear the highest bit that can participate in this carry chain, namely bit p-1. Then x+1 restores that bit and propagates appropriately, causing the OR result to reconstruct the original number. Any smaller modification would fail to produce the target, and any larger modification would yield a larger x.

Python Solution

from typing import List

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        result = []

        for num in nums:
            if num == 2:
                result.append(-1)
                continue

            pos = 0
            while (num >> pos) & 1:
                pos += 1

            result.append(num - (1 << (pos - 1)))

        return result

The implementation processes each number independently.

When the number equals 2, we immediately append -1 because no valid solution exists.

For every other prime, which is necessarily odd, we search for the first zero bit. The loop advances while the current bit equals 1. Once the first zero bit is found, its position is stored in pos.

If the first zero occurs at position pos, then the minimum valid answer is obtained by subtracting 2^(pos-1) from the original number. This effectively clears the bit immediately below the first zero.

The resulting value is appended to the answer array.

Go Solution

func minBitwiseArray(nums []int) []int {
	result := make([]int, 0, len(nums))

	for _, num := range nums {
		if num == 2 {
			result = append(result, -1)
			continue
		}

		pos := 0
		for ((num >> pos) & 1) == 1 {
			pos++
		}

		result = append(result, num-(1<<(pos-1)))
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

Go uses integer bit shifting in the same way. Since all values are at most $10^9$, there are no overflow concerns when computing powers of two involved in the solution. The result slice is preallocated with capacity len(nums) to avoid unnecessary reallocations.

Worked Examples

Example 1

Input:

nums = [2,3,5,7]

Number = 2

No solution exists.

num	answer
2	-1

Number = 3

Binary:

3 = 11₂

Scanning bits:

Position	Bit
0	1
1	1
2	0

First zero bit is at position 2.

ans = 3 - 2^(2-1)
    = 3 - 2
    = 1

Verification:

1 OR 2 = 3

Number = 5

Binary:

5 = 101₂

Scanning bits:

Position	Bit
0	1
1	0

First zero bit is at position 1.

ans = 5 - 1
    = 4

Verification:

4 OR 5 = 5

Number = 7

Binary:

7 = 111₂

Scanning bits:

Position	Bit
0	1
1	1
2	1
3	0

First zero bit is at position 3.

ans = 7 - 4
    = 3

Verification:

3 OR 4 = 7

Final answer:

[-1,1,4,3]

Example 2

Input:

nums = [11,13,31]

Number = 11

11 = 1011₂

First zero bit is at position 2.

ans = 11 - 2
    = 9

Check:

9 OR 10 = 11

Number = 13

13 = 1101₂

First zero bit is at position 1.

ans = 13 - 1
    = 12

Check:

12 OR 13 = 13

Number = 31

31 = 11111₂

First zero bit is at position 5.

ans = 31 - 16
    = 15

Check:

15 OR 16 = 31

Final answer:

[9,12,15]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log M)	At most 31 bit positions are scanned for each number
Space	O(1)	Excluding the output array

Since nums[i] ≤ 10^9, every number contains at most 30 significant bits. For each element we scan upward until reaching the first zero bit, so the work per element is bounded by a small constant. Therefore the overall complexity is effectively linear in the size of the input array.

Test Cases

from typing import List

s = Solution()

assert s.minBitwiseArray([2, 3, 5, 7]) == [-1, 1, 4, 3]  # provided example 1

assert s.minBitwiseArray([11, 13, 31]) == [9, 12, 15]  # provided example 2

assert s.minBitwiseArray([2]) == [-1]  # smallest prime

assert s.minBitwiseArray([3]) == [1]  # smallest valid odd prime

assert s.minBitwiseArray([5]) == [4]  # single trailing one

assert s.minBitwiseArray([7]) == [3]  # all ones

assert s.minBitwiseArray([17]) == [16]  # binary 10001

assert s.minBitwiseArray([19]) == [17]  # binary 10011

assert s.minBitwiseArray([127]) == [63]  # long run of trailing ones

assert s.minBitwiseArray([3, 5, 11, 13, 31]) == [1, 4, 9, 12, 15]  # mixed inputs

Test Summary

Test	Why
[2]	Verifies the only impossible prime
[3]	Smallest valid odd prime
[5]	First zero bit appears immediately
[7]	Number consisting entirely of ones
[17]	Sparse binary representation
[19]	Multiple trailing ones
[127]	Long carry chain
Mixed array	Verifies independent processing
Example 1	Matches official example
Example 2	Matches official example

Edge Cases

Prime Number 2

The value 2 is special because it is the only even prime. The expression x | (x + 1) is always odd, since one of the two consecutive numbers must have its least significant bit set. Therefore producing 2 is impossible. The implementation explicitly checks for this case and returns -1.

Numbers Consisting Entirely of Ones

Values such as 7, 31, and 127 have binary forms like 111, 11111, and 1111111. A common mistake is assuming there is always a zero bit inside the representation. The algorithm continues scanning beyond the highest set bit until it encounters the first zero bit, which naturally exists at the next position. This correctly produces answers such as 3, 15, and 63.

First Zero Bit Immediately Above the Least Significant Bit

Numbers like 5 (101₂) and 13 (1101₂) have their first zero bit very close to the right side. It is easy to make an off by one error when computing which bit to clear. The implementation carefully subtracts 1 << (pos - 1), where pos is the first zero bit position, ensuring the correct bit is removed.

Large Prime Values Near the Constraint Limit

Primes may be as large as $10^9$. A brute force search would be infeasible. The bit manipulation solution only examines a small number of bits, at most around 31, so performance remains excellent even for the largest allowed inputs.