Minimum Impossible OR - Practice Coding Problems

Minimum Impossible OR - Problem

You are given a 0-indexed integer array nums.

We say that an integer x is expressible from nums if there exist some integers 0 <= index1 < index2 < ... < indexk < nums.length for which nums[index1] | nums[index2] | ... | nums[indexk] = x. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of nums.

Return the minimum positive non-zero integer that is not expressible from nums.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2]

› Output: 4

💡 Note: 1 OR 2 = 3. Expressible: 1, 2, 3. Missing: 4 is the minimum positive integer not expressible.

Example 2 — Single Element

$ Input: nums = [5]

› Output: 1

💡 Note: Only 5 is expressible. 1 is the minimum positive integer not expressible.

Example 3 — Multiple Elements

$ Input: nums = [3,1]

› Output: 2

💡 Note: Expressible: 1, 3, 1|3=3. So expressible are {1,3}. Minimum missing: 2.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of positive integers

OR Combinations

All possible OR values from subsequences

Find Minimum

Smallest positive integer not expressible

Key Takeaway

🎯 Key Insight: OR can only set bits - if no number has bit k set, then 2^k cannot be formed

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that OR operations can only set bits, never unset them. To form any number with bit k set, we need at least one input number with bit k set. Best approach is checking each power of 2 until we find one that cannot be formed. Time: O(n × log(max)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Power of 2 Insight	O(n × log(max))	O(1)	Check if powers of 2 are present - if not, that power is the answer
Generate All Possible OR Values	O(n × k)	O(k)	Generate all possible OR combinations from subsequences

Power of 2 Insight — Algorithm Steps

Check each power of 2 starting from 1
For each power 2^k, see if any number has bit k set
Return the first power of 2 that cannot be formed

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Powers

Check if 1, 2, 4, 8... can be formed

Bit Analysis

See which numbers have each bit set

Find Gap

First power of 2 with no corresponding bit

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    // Check each power of 2
    int power = 1;
    
    while (power > 0) { // Avoid overflow
        // Check if any number has this bit set
        bool canForm = false;
        for (int i = 0; i < numsSize; i++) {
            if (nums[i] & power) {
                canForm = true;
                break;
            }
        }
        
        if (!canForm) {
            return power;
        }
            
        if (power > 1000000000) break; // Prevent overflow
        power *= 2;
    }
    
    return power;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = line + 1; // Skip '['
    while (*ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        nums[numsSize++] = atoi(ptr);
        while (*ptr != ',' && *ptr != ']') ptr++;
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max))

Check each bit position up to log(max value) for all n numbers

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

15.0K Views

Medium Frequency

~25 min Avg. Time

420 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

Power of 2 Insight — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler