Construct the Minimum Bitwise Array I

Problem Description

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.

Key Insights

• The bitwise OR operation combines bits such that if either bit is 1, the result is 1.
• For a prime number p, it can be expressed as a OR (a + 1) where a must be chosen carefully.
• The only valid ans[i] values will be from 0 to p-1.
• For each prime number p, if p is odd, it can be represented as a = p - 1 - 1 which leads to p = (p - 1) OR p.
• If p is even (which only includes 2), there are no valid ans[i] values that satisfy the condition.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we iterate through the nums array and for each prime number, we check if it is even or odd. If it is even, we set ans[i] to -1. If it is odd, we calculate the smallest integer a such that a OR (a + 1) = nums[i]. This is done by setting a = nums[i] - 1 - (nums[i] & -nums[i]), where nums[i] & -nums[i] gives the lowest set bit. We then fill the ans array accordingly.

Code Solutions