# Construct the Minimum Bitwise Array II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-the-minimum-bitwise-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/construct-the-minimum-bitwise-array-ii
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Aon](https://scaleengineer.com/companies/aon)
---
## Problem
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] <= 109`
* `nums[i]` is a prime number.

# Approaches
## Brute Force Search
This approach involves a straightforward search for the solution. For each number `nums[i]` in the input array, we iterate through all possible candidate values for `ans[i]` starting from 0. The first value that satisfies the condition `ans[i] OR (ans[i] + 1) == nums[i]` is guaranteed to be the minimum possible value. If no such value is found up to `nums[i] - 1`, we conclude that no solution exists.
**Time:** O(N * M), where N is the length of `nums` and M is the maximum value in `nums`. Given M can be up to 10^9, this approach is not feasible. · **Space:** O(N) for the output array. If the output array is not considered, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Correctly finds the minimum solution if one exists within the time limits.
**Cons:** Extremely inefficient due to the nested loop structure.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints, as `nums[i]` can be up to 10^9.
### Explanation
The algorithm iterates through each number in the `nums` array. For each number, say `num`, it starts a search for a corresponding `ans` value, let's call it `x`. The search for `x` begins at 0 and goes up to `num - 1`. We know the solution `x` cannot be greater than or equal to `num` because `x | (x+1)` would be at least `num+1`. For each `x`, it checks if `x | (x + 1)` equals `num`. Since we are iterating `x` in increasing order, the first `x` that satisfies this condition is the minimum solution. If the loop finishes without finding a solution, we set the answer to -1.

```java
class Solution {
    public int[] constructArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int result = -1;
            // The smallest solution x must be less than num because x | (x+1) >= x+1.
            // So, num >= x+1, which means x <= num - 1.
            for (int x = 0; x < num; x++) {
                if ((x | (x + 1)) == num) {
                    result = x;
                    break;
                }
            }
            ans[i] = result;
        }
        return ans;
    }
}
```
### Algorithm
- Initialize an answer array `ans` of the same size as `nums`.
- For each element `num` at index `i` in `nums`:
  - Set a flag `found = false`.
  - Iterate with a variable `x` from `0` up to `num - 1`. The smallest solution `x` must satisfy `x | (x+1) >= x+1`, so `num >= x+1`, which implies `x <= num - 1`.
  - In each iteration, check if `x | (x + 1) == num`.
  - If the condition is true, we have found the smallest `x`. Set `ans[i] = x`, set `found = true`, and break the inner loop.
  - After the loop, if `found` is still `false`, it means no solution exists. Set `ans[i] = -1`.
- Return the `ans` array.

## Mathematical and Bitwise Analysis
A highly efficient approach can be developed by analyzing the bitwise properties of the expression `x | (x + 1)` and how it relates to `y = nums[i]`. By considering the parity of `x` and the last two bits of `y` (i.e., `y % 4`), we can establish a set of rules that directly compute the smallest `x` without any iteration or searching.
**Time:** O(N), where N is the length of `nums`. Each number in the input array is processed in constant time. · **Space:** O(N) for the output array. The auxiliary space complexity is O(1).
**Pros:** Extremely efficient, with an optimal time complexity.; Directly computes the answer using arithmetic and bitwise operations, avoiding any loops or searches for each number.
**Cons:** The logic is non-trivial and requires careful mathematical and bitwise reasoning to derive and prove correctness.
### Explanation
This optimal solution is based on a case-by-case analysis of the input number `num`.

1.  **Case `num = 2`**: `2` is the only even prime. It can be shown that no integer `x` satisfies `x | (x+1) = 2`. So, the answer is -1.

2.  **Case `num` is an odd prime**: We analyze based on the last two bits of `num`.
    - **If `num % 4 == 1`** (binary ends in `...01`): For `x | (x+1)` to have a 0 at the second-to-last bit, `x` must be an even number. For an even `x`, `x | (x+1)` simplifies to `x+1`. Thus, `x+1 = num`, which gives `x = num - 1`. This is the only possible solution, and therefore the minimum.
    - **If `num % 4 == 3`** (binary ends in `...11`): In this case, `x` could be even or odd. The even solution is `x_even = num - 1`. We must also find the smallest odd solution `x_odd` and compare. 
        - If `num` is a Mersenne prime (a prime of the form `2^k - 1`, like 3, 7, 31), the smallest odd solution is `x_odd = (num - 1) / 2`. This is always smaller than `x_even`.
        - If `num` is not a Mersenne prime (like 11, 19, 23), the smallest odd solution is `x_odd = num - 2`. This is also smaller than `x_even`.

This logic allows for a constant-time calculation for each number.

```java
class Solution {
    public int[] constructArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 2) {
                ans[i] = -1;
            } else if (num % 4 == 1) {
                ans[i] = num - 1;
            } else { // num % 4 == 3
                // Check if num is a Mersenne prime (of the form 2^k - 1)
                // A number n is of the form 2^k-1 iff (n+1) & n == 0
                if (((long)num + 1 & num) == 0) {
                    ans[i] = (num - 1) / 2;
                } else {
                    ans[i] = num - 2;
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize an answer array `ans`.
- Iterate through each `num` at index `i` in `nums`:
  - If `num == 2`, set `ans[i] = -1`.
  - If `num % 4 == 1`, the solution must be even. Set `ans[i] = num - 1`.
  - If `num % 4 == 3`:
    - Check if `num` is a Mersenne prime (a prime of the form `2^k - 1`). This can be checked with the bitwise trick `((long)num + 1 & num) == 0`.
    - If it is a Mersenne prime, the smallest solution is `ans[i] = (num - 1) / 2`.
    - Otherwise, the smallest solution is `ans[i] = num - 2`.
- Return the `ans` array.

# Solutions
### Java

```java
class Solution {
public
  int[] minBitwiseArray(List<Integer> nums) {
    int n = nums.size();
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      int x = nums.get(i);
      if (x == 2) {
        ans[i] = -1;
      } else {
        for (int j = 1; j < 32; ++j) {
          if ((x >> j & 1) == 0) {
            ans[i] = x ^ 1 << (j - 1);
            break;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minBitwiseArray(vector<int> &nums) {
    vector<int> ans;
    for (int x : nums) {
      if (x == 2) {
        ans.push_back(-1);
      } else {
        for (int i = 1; i < 32; ++i) {
          if (x >> i & 1 ^ 1) {
            ans.push_back(x ^ 1 << (i - 1));
            break;
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]: ans = [] for x in nums: if x == 2: ans . append(- 1) else: for i in range(1, 32): if x >> i & 1 ^ 1: ans . append(x ^ 1 << (i - 1)) break return ans

```