Construct the Minimum Bitwise Array II - Practice Coding Problems

Construct the Minimum Bitwise Array II - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5,7]

› Output: [-1,1,4,3]

💡 Note: For 2: impossible since 2 is the smallest prime and no valid x exists. For 3: 1|2 = 3. For 5: 4|5 = 5. For 7: 3|4 = 7.

Example 2 — Larger Numbers

$ Input: nums = [11,13,31]

› Output: [10,12,30]

💡 Note: For 11: 10|11 = 11. For 13: 12|13 = 13. For 31: 30|31 = 31.

Example 3 — Edge Case

$ Input: nums = [2,2,2]

› Output: [-1,-1,-1]

💡 Note: All elements are 2, which cannot be formed by x OR (x+1) for any non-negative x.

Constraints

1 ≤ nums.length ≤ 100
2 ≤ nums[i] ≤ 1000
nums[i] is a prime number

Visualization

Tap to expand

Understanding the Visualization

Input

Array of prime numbers [2,3,5,7]

Process

For each number, find minimum x where x OR (x+1) equals the number

Output

Array of minimum values [-1,1,4,3]

Key Takeaway

🎯 Key Insight: The OR operation with consecutive numbers creates predictable bit patterns that can be mathematically reversed

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is understanding how the OR operation works with consecutive numbers: x OR (x+1) creates specific bit patterns that can be analyzed mathematically. The optimal approach uses bit manipulation to directly compute the minimum value by finding the rightmost bit position that can be cleared. Time: O(n × log k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Search	O(n × k)	O(1)	Try all possible values from 0 upwards until finding one that satisfies the OR condition
Bit Manipulation Analysis	O(n × log k)	O(1)	Analyze bit patterns to directly compute the minimum value without brute force

Brute Force Search — Algorithm Steps

For each number in nums
Try values x = 0, 1, 2, ... until x OR (x+1) == nums[i]
Return first valid x, or -1 if not found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Testing

Begin with x = 0, test if x OR (x+1) equals target

Increment

If not found, try x = 1, then x = 2, etc.

Found

Stop when x OR (x+1) equals the target number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        // Try values from 0 up to a reasonable limit
        for (int x = 0; x <= nums[i]; x++) {
            if ((x | (x + 1)) == nums[i]) {
                result[i] = x;
                found = 1;
                break;
            }
        }
        if (!found) {
            result[i] = -1;
        }
    }
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums, count, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For each of n elements, we may check up to k values where k can be large

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for iteration

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler