Construct the Minimum Bitwise Array I

easy array bit manipulation bitwise OR

Problem

You are given an array nums of n prime integers. Build an array ans of length n so that for every index i the bitwise OR of ans[i] and ans[i] + 1 equals nums[i], that is ans[i] | (ans[i] + 1) == nums[i].

Among all valid choices, each ans[i] must be the minimum possible. If no value works, set ans[i] = -1.

Inputnums = [2, 3, 5, 7]

Output[-1, 1, 4, 3]

2 has no solution. 1 | 2 = 3, 4 | 5 = 5, and 3 | 4 = 7, each being the smallest that works.

nums (comma-separated primes)

def minBitwiseArray(nums):
    ans = []
    for num in nums:                     # solve each prime independently
        found = -1                       # default: no x satisfies the rule
        for x in range(num):             # x | (x+1) >= num, so x must be < num
            if (x | (x + 1)) == num:     # smallest x found first
                found = x
                break
        ans.append(found)
    return ans

function minBitwiseArray(nums) {
  const ans = [];
  for (const num of nums) {              // solve each prime independently
    let found = -1;                      // default: no x satisfies the rule
    for (let x = 0; x < num; x++) {      // x | (x+1) >= num, so x must be < num
      if ((x | (x + 1)) === num) {       // smallest x found first
        found = x;
        break;
      }
    }
    ans.push(found);
  }
  return ans;
}

int[] minBitwiseArray(int[] nums) {
    int[] ans = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {  // solve each prime independently
        int num = nums[i], found = -1;       // default: no x satisfies the rule
        for (int x = 0; x < num; x++) {      // x | (x+1) >= num, so x must be < num
            if ((x | (x + 1)) == num) {      // smallest x found first
                found = x;
                break;
            }
        }
        ans[i] = found;
    }
    return ans;
}

vector<int> minBitwiseArray(vector<int>& nums) {
    vector<int> ans;
    for (int num : nums) {                   // solve each prime independently
        int found = -1;                      // default: no x satisfies the rule
        for (int x = 0; x < num; x++) {      // x | (x+1) >= num, so x must be < num
            if ((x | (x + 1)) == num) {      // smallest x found first
                found = x;
                break;
            }
        }
        ans.push_back(found);
    }
    return ans;
}

Explanation

Each index is an independent puzzle: given a target prime num, find the smallest x with x | (x + 1) == num. Because the indices do not interact, we just loop over nums and solve one at a time.

The key observation is that x | (x + 1) is always at least x, and in fact at least num when it equals num. So a valid x is strictly smaller than num. That bounds the search: we only need to try x = 0, 1, 2, …, num − 1.

Since the constraints are tiny (num ≤ 1000), we scan candidates in increasing order and return the first one that matches. Scanning upward guarantees the result is the minimum automatically.

Why might no answer exist? x | (x + 1) sets a contiguous low run of bits, so its binary form ends in a block of ones. The value 2 is 10 in binary — it can never be produced this way, so the answer there is -1. For example, 1 | 2 = 11₂ = 3, 4 | 5 = 101₂ = 5, and 3 | 4 = 111₂ = 7.

Worked example: nums = [2,3,5,7]. Index 0 finds nothing, so -1. Index 1 finds x = 1. Index 2 finds x = 4. Index 3 finds x = 3. Result: [-1, 1, 4, 3].

Time: O(n · max(nums)) Space: O(n)