Skip to main content
Talentd

Construct the Minimum Bitwise Array II - Solution & Explanation

MediumArrayBit Manipulation16 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

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 for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1.
  • For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3.
  • For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5.
  • For 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:

  • For i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11.
  • For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13.
  • For 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 <= 100
  • 2 <= nums[i] <= 109
  • nums[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.

Approach 1: Bit Manipulation Approach

This approach relies on understanding the binary representation of numbers and utilizing bitwise operations effectively. The challenge is to decompose nums[i] into two consecutive numbers whose OR equals nums[i]. The key lies in setting the least significant zero bit in nums[i] to one. If there is no such zero, it is impossible to achieve and thus the result should be -1.

The algorithm iterates over each element in nums. If num is odd, it itself is a valid answer because odd numbers already meet the condition. For even num, we attempt to find ans[i] by identifying the smallest number y such that y OR (y + 1) = num. This is done by checking if removing the least significant set bit yields a number that still satisfies the condition.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the nums array.
Space Complexity: O(1), if we don't consider the output array as additional space.

Try this approach in the editor →

Approach 2: Brute-force Approach

This is a straightforward method that attempts to find solutions for each element in the nums array by brute-force checking each potential value for ans[i]. This approach is inefficient but guarantees correctness as it checks all possibilities.

This brute-force Python function iterates through each possible value from 0 to num - 1 for each element in nums and checks if it satisfies the condition. Once a valid ans is found, it stops further checks and moves to the next number. If no valid answer is found, it appends -1.

Code

Python

Python

Complexity

Time Complexity: O(n * m), where n is the size of the nums array and m is the average value in nums.
Space Complexity: O(1), not counting the output array.

Try this approach in the editor →

Approach 3: Bit Manipulation

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

If nums[i] is odd, suppose nums[i] = 0b1101101. Since a \lor (a + 1) = nums[i], this is equivalent to changing the last 0 bit of a to 1. To solve for a, we need to change the bit after the last 0 in nums[i] to 0. We start traversing from the least significant bit (index 1) and find the first 0 bit. If it is at position i, we change the (i - 1)-th bit of nums[i] to 1, i.e., ans[i] = nums[i] \oplus 2^{i - 1}.

By traversing all elements in nums, we can obtain the answer.

The time complexity is O(n times log M), where n and M are the length of the array nums and the maximum value in the array, respectively. Ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bit Manipulation Approach

Time Complexity: O(n), where n is the number of elements in the nums array.
Space Complexity: O(1), if we don't consider the output array as additional space.

Brute-force Approach

Time Complexity: O(n * m), where n is the size of the nums array and m is the average value in nums.
Space Complexity: O(1), not counting the output array.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SearchO(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

Video Solution

Construct the Minimum Bitwise Array I & II | LeetCode 3314 & 3315 | Brute & Optimal Solution • Sanyam IIT Guwahati • 1,875 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Construct the Minimum Bitwise Array II easy or hard?
Construct the Minimum Bitwise Array II is generally classified as a Medium problem. The implementation is simple once you recognize the binary pattern behind a | (a + 1), but identifying the trailing-ones property requires familiarity with bit manipulation techniques.
Construct the Minimum Bitwise Array II Python/Java solution
In Python, Java, C++, or JavaScript the implementation follows the same logic: iterate through nums, check if the number is even, count trailing 1 bits, and subtract 2^(k-1) to construct the minimal value. Each language uses built-in bit operators to perform the calculation efficiently.
How to solve Construct the Minimum Bitwise Array II in O(n)?
Iterate through the array and analyze the binary representation of each value. If the number is even, return -1 because a | (a + 1) always produces an odd number. Otherwise count the trailing 1 bits and compute the answer using nums[i] - 2^(k-1). This converts the problem into a simple bit calculation per element.
What is the best approach for Construct the Minimum Bitwise Array II?
The best approach uses a bit manipulation observation about the result of a | (a + 1). The OR of consecutive integers always produces a number with trailing 1 bits. By counting the trailing 1s in nums[i], you can directly compute the minimum valid a as nums[i] - 2^(k-1). This solution runs in O(n) time with O(1) space.
Is Construct the Minimum Bitwise Array II asked at Google/Amazon/Meta?
Bit manipulation problems with binary pattern recognition frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of OR/AND bit construction and trailing-bit logic are common in coding rounds because they test low-level reasoning about binary operations.
What data structure is used in Construct the Minimum Bitwise Array II?
The problem mainly relies on arrays and bit manipulation. The array stores the input and output values, while bit operations are used to inspect trailing 1 bits and compute the minimal valid number efficiently.
What is the time complexity of Construct the Minimum Bitwise Array II?
The optimal solution runs in O(n) time because each element is processed once with constant-time bit operations. Space complexity is O(1) apart from the output array. A brute force approach can degrade to O(n * m) where m is the search range for a candidate value.

Ready to solve this problem?

Practice Construct the Minimum Bitwise Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays