Skip to main content
Talentd

Construct the Minimum Bitwise Array I - Solution & Explanation

EasyArrayBit Manipulation16 min readAsked at: Amazon, Microsoft, Aon +2
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] <= 1000
  • nums[i] is a prime number.

Approach Overview

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 1: Bit Manipulation to Find Minimum `ans[i]`

To solve the problem, note that for any number x, the result of x OR (x + 1) will be a number that has all the bits of x, plus at least one more.

Thus, for any prime number p, the smallest number x for which x OR (x + 1) = p happens to be when we can have x such that it contains all bits of p-1.

Thus, iterate over powers of two combinations that are not part of p's binary representation to find the smallest ans[i].

The logic here is to compute if a number p can be generated using the pattern which primarily requires finding p-1 equivalent truths in forming the OR.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

Time Complexity: O(1) for checking a bitwise condition.
Space Complexity: O(n) for storing the answer.

Try this approach in the editor →

Approach 2: Iterative Check for OR Condition

Instead of computing directly using bit manipulation, this approach checks in a brute-force like manner from 0 upwards to verify which x satisfies x OR (x + 1) = p, thus ensuring minimal x.

This solution takes up every number from 0 to ensure that if the direct OR comparison backs to the respected prime number, output is appended.

Code

JavaCC#

Java

C

C#

Complexity

Time Complexity: O(1000 * n) where 1000 iterations max for each number.
Space Complexity: O(n) for storing the answer.

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 to Find Minimum `ans[i]`

Time Complexity: O(1) for checking a bitwise condition.
Space Complexity: O(n) for storing the answer.

Iterative Check for OR Condition

Time Complexity: O(1000 * n) where 1000 iterations max for each number.
Space Complexity: O(n) for storing the answer.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Check for OR ConditionO(n * v)O(1)Good for understanding the definition or when values are very small
Bit Manipulation Using Trailing OnesO(n)O(1)Optimal approach for interviews and large inputs

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 I easy or hard?
Construct the Minimum Bitwise Array I is classified as an Easy problem. The challenge lies in recognizing the bit pattern formed by x | (x + 1). Once that observation is clear, the implementation is short and runs in linear time.
Construct the Minimum Bitwise Array I Python/Java solution
The solution is straightforward in Python, Java, C++, or JavaScript because all languages support bitwise operators. Iterate through nums, detect even values for -1, and compute the minimal candidate using trailing-bit manipulation. Each implementation runs in O(n) time.
How to solve Construct the Minimum Bitwise Array I in O(n)?
Iterate through the array once. For each number, first check if it is even because even numbers cannot be formed by x | (x+1). For odd numbers, count the trailing 1 bits and flip the correct bit to compute the smallest valid x. This avoids brute-force searching and keeps the algorithm linear.
What is the best approach for Construct the Minimum Bitwise Array I?
The best approach uses bit manipulation. Observe that x | (x + 1) produces a number whose least significant bits are all 1s. If nums[i] is even, no solution exists. If it is odd, count the trailing ones and flip the appropriate bit to construct the minimum x. This processes each element in O(1) time.
Is Construct the Minimum Bitwise Array I asked at Google/Amazon/Meta?
Problems involving bit manipulation and consecutive integer patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of OR/AND bit transformation questions are common because they test low-level reasoning and optimization skills.
What data structure is used in Construct the Minimum Bitwise Array I?
The problem primarily uses arrays for input and output. The core logic relies on bit manipulation operations such as OR, XOR, and bit shifting rather than complex data structures.
What is the time complexity of Construct the Minimum Bitwise Array I?
The optimal bit manipulation approach runs in O(n) time where n is the size of the input array. Each element is processed using constant-time bit operations. Space complexity is O(1) apart from the output array.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays