Construct the Minimum Bitwise Array I

Difficulty: Easy | Acceptance: 85.20% | Paid: No Topics: Array, Bit Manipulation

You are given an array nums of positive integers.

For each nums[i], find the smallest integer x such that x & (x + 1) == nums[i]. If no such x exists, return -1.

Return the resulting array.

• Examples
• Constraints
• Mathematical Optimization
• Brute Force Simulation

Examples

Example 1:

Input: nums = [2, 3]
Output: [2, -1]
Explanation: 
For nums[0] = 2, the smallest x is 2 because 2 & 3 = 2.
For nums[1] = 3, there is no x such that x & (x + 1) = 3.

Example 2:

Input: nums = [4, 5]
Output: [4, -1]
Explanation: 
For nums[0] = 4, the smallest x is 4 because 4 & 5 = 4.
For nums[1] = 5, there is no x such that x & (x + 1) = 5.

Constraints

- 1 <= nums.length <= 100
- 2 <= nums[i] <= 1000
- nums[i] is a prime number.

Mathematical Optimization

Intuition The bitwise AND operation x & (x + 1) has a specific property based on the parity of x. If x is even, its least significant bit is 0. Adding 1 only flips this bit to 1, leaving all higher bits unchanged. Thus, x & (x + 1) equals x itself. If x is odd, the least significant bit is 1, and x + 1 is even, resulting in a least significant bit of 0 in the AND result. Therefore, x & (x + 1) is always even. This means if nums[i] is odd, no solution exists. If nums[i] is even, x = nums[i] is the smallest valid solution because x & (x + 1) <= x.

Steps

• Initialize an empty list result to store the answers.
• Iterate through each number num in the input array nums.
• Check if num is even using the modulo operator (num % 2 == 0).
• If it is even, append num to result (since num & (num + 1) == num).
• If it is odd, append -1 to result (since x & (x + 1) is always even).
• Return the result list.

class Solution:
    def minBitwiseArray(self, nums: list[int]) -> list[int]:
        result = []
        for num in nums:
            if num % 2 == 0:
                result.append(num)
            else:
                result.append(-1)
        return result

Complexity

• Time: O(N), where N is the length of the array. We iterate through the array once.
• Space: O(N) to store the result array. (O(1) extra space if not counting output).
• Notes: This is the optimal solution with linear time complexity.

Brute Force Simulation

Intuition We can iterate through possible values of x for each nums[i] to find the smallest valid x. Since x & (x + 1) <= x, we know that x must be at least nums[i]. We can start checking from x = 1 up to nums[i] (or slightly higher) to see if the condition x & (x + 1) == nums[i] holds. This approach verifies the mathematical property by exhaustive search within a limited range.

Steps

• Initialize an empty list result.
• Iterate through each number num in nums.
• Initialize a variable ans = -1.
• Loop x from 1 to num (inclusive).
• Check if x & (x + 1) == num.
• If true, update ans = x and break the loop (since we are iterating upwards, the first found is the smallest).
• Append ans to result.
• Return result.

class Solution:
    def minBitwiseArray(self, nums: list[int]) -> list[int]:
        result = []
        for num in nums:
            ans = -1
            # x & (x + 1) <= x, so we only need to check up to num
            for x in range(1, num + 1):
                if x & (x + 1) == num:
                    ans = x
                    break
            result.append(ans)
        return result

Complexity

• Time: O(N * M), where N is the length of the array and M is the maximum value in nums. In the worst case, we iterate up to nums[i] for each element.
• Space: O(N) to store the result array.
• Notes: This approach is inefficient for large values of nums[i] (up to 10⁹) and will result in Time Limit Exceeded on LeetCode, but serves as a good baseline for understanding the problem.