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 II

Number: 3611

Difficulty: Medium

Paid? No

Companies: Aon

Problem Description

Given an array nums of n prime numbers, for each prime number p = nums[i] find the minimum non-negative integer ans[i] such that ans[i] OR (ans[i] + 1) equals p. If no such ans[i] exists, set ans[i] to -1. The objective is to minimize each ans[i].

Key Insights

  • For any integer x, when you add 1, the binary representation flips the trailing ones to zeros and the first encountered 0 to 1.
  • When x is of the form A0 followed by r ones, then x + 1 becomes A1 followed by r zeros. Their OR produces A1 followed by r ones.
  • Therefore a candidate x that satisfies x OR (x+1) = p must be such that p has a suffix of r+1 ones. In particular, p + 1 must be divisible by a power of 2, say d = 2^(r+1).
  • Using this property, p can be represented as: p = A * 2^(r+1) + (2^(r+1) - 1) where A is a non-negative integer.
  • The minimal x with trailing r ones that produces p on OR will be: x = A * 2^(r+1) + (2^r - 1)
  • In implementation, for each prime p, we compute p+1 and find the highest power of 2, d, dividing it. If d < 2 (i.e. if p+1 is odd) then no solution exists; otherwise, set A = (p+1) / d - 1 and compute x accordingly.

Space and Time Complexity

Time Complexity: O(n * log(p)), where for each number we determine the highest power of 2 factor in O(log(p)). Space Complexity: O(n) for storing the answer array.

Solution

The solution leverages bit manipulation and number theory. For every prime number p in the input:

  1. Compute S = p + 1.
  2. Find the largest power of 2 (denoted as d = 2^(r+1)) that divides S.
  3. If d is at least 2, then p must be expressible in the form: p = A * d + (d - 1); here, d - 1 is (2^(r+1) - 1). Solve for A = (S / d) - 1.
  4. The answer x (i.e. ans[i]) is then constructed as: x = A * d + (d/2 - 1). This x is the smallest number whose binary structure is: a prefix A, followed by a 0 bit, and then r ones.
  5. If p+1 has no factor of 2 (i.e. d < 2), then no such x exists and ans[i] is set to -1. This method directly computes the minimal candidate by working backwards from the structural conditions imposed by the bitwise OR of x and (x+1).

Code Solutions

# Python solution
class Solution:
    def constructMinimumBitwiseArray(self, nums):
        # Initialize result list.
        ans = []
        for p in nums:
            S = p + 1
            # Find the highest power of 2 that divides (p+1)
            d = 1
            while S % (d * 2) == 0:
                d *= 2
            # d should be >= 2 representing 2^(r+1) with r >= 0
            if d < 2:
                ans.append(-1)
            else:
                # Calculate A = (p+1) / d - 1
                A = S // d - 1
                # Compute x = A * d + (d/2 - 1)
                x = A * d + (d // 2 - 1)
                ans.append(x)
        return ans

# Example usage:
# sol = Solution()
# print(sol.constructMinimumBitwiseArray([2,3,5,7]))
← Back to All Questions