Construct the Minimum Bitwise Array II

MEDIUM

Description

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] <= 10⁹
nums[i] is a prime number.

Approaches

Checkout 2 different approaches to solve Construct the Minimum Bitwise Array II. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(N) for the output array. If the output array is not considered, the space complexity is O(1).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Construct the Minimum Bitwise Array II. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Construct the Minimum Bitwise Array II

Patterns:

Bit Manipulation

Data Structures:

Array

Companies:

Aon |