# Construct the Minimum Bitwise Array I
**Difficulty:** EASY
[External](https://leetcode.com/problems/construct-the-minimum-bitwise-array-i)
Canonical: https://scaleengineer.com/dsa/problems/construct-the-minimum-bitwise-array-i
**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] <= 1000`
* `nums[i]` is a prime number.

# Approaches
## Brute Force Search
This approach uses a straightforward brute-force search. For each element `num` in the `nums` array, we iterate through all possible candidate values for `ans[i]` from `0` up to `num - 1`. For each candidate `x`, we check if it satisfies the condition `x | (x + 1) == num`. Since we are iterating from the smallest possible value upwards, the first candidate that satisfies the condition is guaranteed to be the minimum.
**Time:** O(N * M), where N is the number of elements in `nums` and M is the maximum value in `nums`. For each of the N numbers, we iterate up to M times. Given the constraints (N <= 100, M <= 1000), this is roughly 100 * 1000 = 10^5 operations, which is efficient enough. · **Space:** O(N) to store the output array `ans`. The auxiliary space complexity is O(1).
**Pros:** Simple to understand and implement.; Guaranteed to find the correct minimum value if one exists.; Sufficiently fast for the given constraints.
**Cons:** The time complexity is dependent on the magnitude of the numbers in the input array, which can be inefficient if the numbers are very large.; It is a naive approach that doesn't leverage the underlying mathematical properties of the bitwise OR operation.
### Explanation
The algorithm proceeds as follows:

- Initialize an integer array `ans` with the same length as `nums` to store the results.
- Iterate through the `nums` array from `i = 0` to `n-1`.
- For each `nums[i]`, start an inner loop with a variable `x` from `0` up to `nums[i] - 1`.
- In the inner loop, compute `x | (x + 1)` and check if it equals `nums[i]`.
- If the condition is met, we have found the smallest `x`. We set `ans[i] = x` and break out of the inner loop to proceed to the next number in `nums`.
- To handle cases where no solution is found, we can use a flag or initialize `ans[i]` to `-1` before the inner loop. If the inner loop finishes without finding a solution, `ans[i]` will remain `-1`.
- After iterating through all numbers in `nums`, return the `ans` array.

```java
class Solution {
    public int[] constructMinimizingBitwiseArray(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;
            // Search space for x is [0, num - 1]
            for (int x = 0; x < num; x++) {
                if ((x | (x + 1)) == num) {
                    result = x;
                    break; // Found the smallest x, no need to check further
                }
            }
            ans[i] = result;
        }

        return ans;
    }
}
```
### Algorithm
The core idea of this approach is to exhaustively search for the smallest possible value for `ans[i]`.

1.  For each number `num` in the input array `nums`, we need to find the smallest non-negative integer `x` such that `x OR (x + 1) == num`.
2.  We know that `x OR (x + 1)` will always be greater than or equal to `x + 1`. Therefore, `num >= x + 1`, which implies `x <= num - 1`.
3.  This gives us a finite search space for `x`: from `0` to `num - 1`.
4.  We can iterate through this range. The first value of `x` that satisfies the condition `x OR (x + 1) == num` will be the smallest, because we are iterating in increasing order.
5.  If the loop completes without finding any such `x`, it means no solution exists for that `num`, and we should assign `-1`.

## Analytical Approach with Bit Manipulation
A highly efficient approach can be formulated by analyzing the bitwise properties of the equation `x | (x + 1) = y`. This analysis reveals a direct mathematical relationship between `y` (the value from `nums`) and the minimal `x` (the value for `ans`). This allows us to compute the result in constant time for each number, leading to a linear time solution overall.
**Time:** O(N), where N is the number of elements in `nums`. Each number is processed in constant time using bitwise operations and a direct formula. · **Space:** O(N) to store the output array `ans`. The auxiliary space complexity is O(1).
**Pros:** Extremely efficient with a linear time complexity.; Calculates the result directly without any searching or iteration.; Scales well even if the constraints on the input numbers were much larger.
**Cons:** The derivation of the formula is complex and not immediately obvious.; Requires a deeper understanding of bitwise operations and number properties.
### Explanation
The core of this approach is a formula derived from the structure of `x | (x+1)`.

Let `y = nums[i]`. We are solving `x | (x+1) = y` for the smallest `x`.

- **Case 1: `y` is even.**
  Since `nums[i]` are prime, the only even case is `y = 2`. We can check that `0|1=1`, `1|2=3`. No non-negative `x` satisfies `x | (x+1) = 2`. So, `ans[i] = -1`.

- **Case 2: `y` is odd.**
  For any odd `y`, a solution exists. The relationship `y = (x+1) + lsb(x+1) - 1` holds, where `lsb(v)` is the value of the least significant bit of `v` (e.g., `lsb(12) = 4`). This can be rearranged to `y+1 = (x+1) + lsb(x+1)`. This equation implies that solutions for `x` must be of the form `y - 2^k`.

To minimize `x = y - 2^k`, we need to maximize `k`. The largest `k` that yields a valid solution is determined by the number of trailing zeros in `y+1`.

Let `p = Integer.numberOfTrailingZeros(y + 1)`. The formula for the minimal `x` is `x = y - (1 << (p - 1))`.

This single formula covers all odd `y` values:
- If `y = 5`, `y+1 = 6` (binary `110`). `p=1`. `x = 5 - (1 << 0) = 4`.
- If `y = 7`, `y+1 = 8` (binary `1000`). `p=3`. `x = 7 - (1 << 2) = 3`.
- If `y = 11`, `y+1 = 12` (binary `1100`). `p=2`. `x = 11 - (1 << 1) = 9`.

```java
class Solution {
    public int[] constructMinimizingBitwiseArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            int num = nums[i];

            // Since nums[i] is prime, the only even number is 2.
            if (num == 2) {
                ans[i] = -1;
            } else {
                // For any odd prime, a solution exists.
                // The smallest solution x is given by the formula:
                // x = num - 2^(p-1), where p is the number of trailing zeros in num + 1.
                int numPlusOne = num + 1;
                int p = Integer.numberOfTrailingZeros(numPlusOne);
                int powerOf2ToSubtract = 1 << (p - 1);
                ans[i] = num - powerOf2ToSubtract;
            }
        }

        return ans;
    }
}
```
### Algorithm
This method is based on a mathematical derivation from the properties of bitwise operations.

1.  First, handle the special case where `num` is the prime `2`. There is no non-negative integer `x` for which `x | (x+1) = 2`. So, if `num = 2`, the answer is `-1`.
2.  For any odd prime `num`, a solution `x` can be found. It can be proven that any solution `x` must be of the form `x = num - 2^k` for some integer `k >= 0`.
3.  To find the *minimum* `x`, we must subtract the *largest* possible valid power of two, `2^k`, from `num`.
4.  The correct value of `k` is related to the binary representation of `num + 1`. Let `p` be the number of trailing zeros in `num + 1`. The largest valid `2^k` we can subtract is `2^(p-1)`.
5.  Thus, the smallest solution `x` is given by the formula: `x = num - (1 << (p - 1))`, where `p` is the number of trailing zeros in `num + 1`.
6.  The number of trailing zeros can be efficiently calculated using built-in functions like `Integer.numberOfTrailingZeros()`.

# 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

```