Bit manipulation can often feel like magic, but it is actually a precise set of rules governing how computers store data. In this challenge, we explore the relationship between a number and its successor to find a specific pattern in the binary landscape.

---

Problem Summary

You’re given: An array of prime integers called nums.

Your goal: For each number, find the smallest possible integer ans[i] such that the bitwise OR of ans[i] and ans[i] + 1 equals the original number. If no such integer exists, return -1.

---

Intuition

The core of this problem lies in the operation . In binary, when you add 1 to a number, the trailing sequence of 1s (on the right) "flips" to 0s, and the first 0 from the right becomes a 1.

For example:

• If (binary 1001), then (binary 1010).
• (which is 11).

Notice that the OR operation effectively "fills in" the bit that changed during the addition. Specifically, it keeps all the original 1s and adds the new 1 created by the carry-over.

To minimize ans[i], we need to find the rightmost group of continuous 1s in the binary representation of nums[i]. By changing the most significant bit of that specific group of 1s to a 0, we create our candidate for ans[i]. When we add 1 back to this candidate, it flips that 0 (and all trailing 0s) back to 1s, satisfying the condition while keeping the value as small as possible.

Note on Prime Numbers: The only even prime is 2. For 2 (binary 10), there is no solution because and . Therefore, 2 always results in -1.

---

Walkthrough: Understanding the Examples

Let’s look at nums = [11].

1. Binary Representation: 11 in binary is 1011.
2. Find the rightmost group of 1s: The 1s at the end are ...11.
3. Identify the leading bit of that group: The group starts at the position (the 2s place).
4. The Logic:
5. If we take 11 and subtract that specific bit (2), we get .
6. Binary of 9 is 1001.
7. Binary of (which is 10) is 1010.

1001 OR 1010 = 1011 (which is 11). 1.

Result: 9 is our answer.

---

Code Blocks

C++

class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
vector<int> ans;

for (const int num : nums) {
// Prime 2 is a special case that cannot satisfy the condition
if (num == 2) {
ans.push_back(-1);
} else {
ans.push_back(num - getLeadingOneOfLastGroupOfOnes(num));
}
}

return ans;
}

private:
int getLeadingOneOfLastGroupOfOnes(int num) {
int leadingOne = 1;
// Find the first 0 bit starting from the right
while ((num & leadingOne) > 0) {
leadingOne <<= 1;
}
// Shift back to get the highest 1-bit in the trailing sequence of 1s
return leadingOne >> 1;
}
};

Python

class Solution:
def minBitwiseArray(self, nums: list[int]) -> list[int]:
ans = []

for num in nums:
if num == 2:
ans.append(-1)
else:
# Find the leading 1 of the trailing group of ones
leading_one = 1
while (num & leading_one) > 0:
leading_one <<= 1

# Use shift-right to pinpoint the bit to subtract
ans.append(num - (leading_one >> 1))

return ans

JavaScript

/**
* @param {number[]} nums
* @return {number[]}
*/
var minBitwiseArray = function(nums) {
return nums.map(num => {
if (num === 2) return -1;

let leadingOne = 1;
// Find the first 0-bit to identify the end of the trailing 1s
while ((num & leadingOne) > 0) {
leadingOne <<= 1;
}

// Subtract half of the leadingOne value to flip the correct bit
return num - (leadingOne >> 1);
});
};

---

Key Takeaways

• Bitwise Carry-over: Adding 1 to a binary number affects all trailing 1s, turning them into 0s and making the first 0-bit a 1.
• Minimalist Logic: To minimize the answer, we target the highest possible bit within the lowest contiguous block of 1s to flip.
• Edge Case Handling: Recognizing that parity (even vs. odd) matters in bitwise operations, especially with the unique property of the prime number 2.

---

Final Thoughts

This problem is an excellent example of how bitwise manipulation is used in low-level systems programming and cryptography. In real-world scenarios, these types of operations are used to manage memory flags, optimize search algorithms, or even handle permissions in a file system. Understanding how bits flip during arithmetic operations like addition is a fundamental skill for high-performance computing.