We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct the Minimum Bitwise Array I

Number: 3605

Difficulty: Easy

Paid? No

Companies: Aon

Problem Description

Given an array nums of n prime numbers (each at least 2), construct an array ans of the same length such that for every index i the equation   ans[i] OR (ans[i] + 1) = nums[i] holds. In addition, each ans[i] should be minimized. If no nonnegative integer exists that satisfies the condition for nums[i], set ans[i] = -1.

For example: • Input: nums = [2,3,5,7] Output: [-1,1,4,3] Explanation:   – For nums[0]=2, no answer exists.   – For nums[1]=3, the smallest ans is 1 since 1 OR 2 = 3.   – For nums[2]=5, choosing ans=4 works because 4 OR 5 = 5.   – For nums[3]=7, ans=3 works since 3 OR 4 = 7.

Key Insights

  • Since the operation involves OR on consecutive numbers (X and X+1), it is crucial to understand how their binary representations combine.
  • For an odd number P (since all primes except 2 are odd), one way to “build” P from two consecutive numbers is to select a candidate X of the form P – d, where d is a power of 2.
  • The equation becomes (P – d) OR (P – d + 1) = P. Notice that a larger d produces a smaller candidate X. Our goal is to minimize X.
  • For each candidate prime P, iterate over powers of 2 (d) that are less than P, starting from the largest. For the first d that makes the equation hold true, choose X = P – d.
  • If no such power of 2 works or if P is 2 (the only even prime), then the answer is –1.

Space and Time Complexity

Time Complexity: O(n · log(max(P))) where max(P) is the maximum value in nums. (For each number, we iterate over at most O(log(max(P))) powers-of-two.) Space Complexity: O(n) for storing the output array.

Solution

The solution uses a straightforward iterative approach over each prime number in the input array. For each number P, if P equals 2 we immediately set the answer to –1 since no nonnegative X satisfies the condition. Otherwise, we iterate over possible powers of 2 (d) in descending order (largest d such that d < P). For each candidate X = P – d we check if X OR (X + 1) equals P. Once found, we save this minimal X and break out of the loop. If no candidate works, we set the answer for that P to –1.

Data structures used:

  • An output array to store answers.
  • Simple loop iterations and bitwise OR operations.

The key trick is to notice that the candidate X always comes as a “shift” from P by subtracting a power-of-two factor. By iterating from the largest possible power-of-two to the smallest, we guarantee that we find the minimum possible X satisfying the condition.

Code Solutions

Below are code solutions with line-by-line comments in Python, JavaScript, C++, and Java.

# Python solution

def constructMinimumBitwiseArray(nums):
    # Function to compute the answer for each prime number in nums.
    def findCandidate(P):
        # If P is 2, no valid candidate exists (based on problem description)
        if P == 2:
            return -1
        # Initialize candidate variable to -1 (assume not found)
        candidate = -1
        # Generate all powers of 2 less than P.
        # Start from highest power of two less than P.
        power = 1
        while power * 2 < P:
            power *= 2
        # Try powers of two in descending order.
        while power >= 1:
            X = P - power  # potential candidate
            # Check if X OR (X+1) equals P
            if (X | (X + 1)) == P:
                return X  # return immediately, minimal found since we start with largest subtraction
            power //= 2
        return -1
    
    # Process each value in nums.
    ans = []
    for num in nums:
        ans.append(findCandidate(num))
    return ans

# Example usage:
nums = [2, 3, 5, 7]
print(constructMinimumBitwiseArray(nums))  # Output: [-1, 1, 4, 3]
← Back to All Questions