Minimum impossible or

Array Bit Manipulation Brainteaser

58.9% acceptance

Feb 25, 2026

382

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_impossible_or(nums: Vec<i32>) -> i32 {
    // Key insight: if all powers of 2 from 1 to 2^k are present in nums,
    // then all values 1..2^(k+1)-1 are expressible.
    // The answer is the smallest power of 2 not in nums.
    let set: std::collections::HashSet<i32> = nums.into_iter().collect();
    let mut power = 1i32;
    while set.contains(&power) {
      power <<= 1;
    }
    power
  }
}