Number of effective subsequences

Array Math Dynamic Programming Bit Manipulation Combinatorics

30.6% acceptance

Feb 25, 2026

You are given an integer array nums. The strength of the array is defined as the bitwise OR of all its elements. A subsequence is considered effective if removing that subsequence strictly decreases the strength of the remaining elements. Return the number of effective subsequences in nums. Since the answer may be large, return it modulo 109 + 7. The bitwise OR of an empty array is 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_effective(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let total_or = nums.iter().fold(0i32, |acc, &x| acc | x);
    if total_or == 0 {
      return 0;
    }
    // Compress: collect only the bits present in total_or (at most 20 for nums[i] <= 10^6)
    let bits: Vec<u32> = (0u32..20).filter(|&b| total_or & (1 << b) != 0).collect();
    let b = bits.len();
    let full_mask = (1usize << b) - 1;
    // Count elements per compressed profile
    let mut f = vec![0i64; 1 << b];
    for &x in &nums {
      let profile: usize = (0..b)
        .filter(|&i| x & (1 << bits[i]) != 0)
        .fold(0, |acc, i| acc | (1 << i));
      f[profile] += 1;
    }
    // SOS DP: g[T] = sum of f[S] for all S ⊆ T
    let mut g = f.clone();
    for i in 0..b {
      for mask in 0..(1usize << b) {
        if mask & (1 << i) != 0 {
          g[mask] += g[mask ^ (1 << i)];
        }
      }
    }
    // Precompute powers of 2 mod MOD
    let mut pow2 = vec![1i64; n + 1];
    for i in 1..=n {
      pow2[i] = pow2[i - 1] * 2 % MOD;
    }
    // Inclusion-exclusion: for each non-empty subset M of bits,
    // free elements = those whose profile shares NO bit with M = g[complement of M]
    let mut answer = 0i64;
    for mask in 1usize..=(full_mask) {
      let popcount = mask.count_ones() as i32;
      let complement = full_mask ^ mask;
      let free = g[complement] as usize;
      if popcount % 2 == 1 {
        answer = (answer + pow2[free]) % MOD;
      } else {
        answer = (answer - pow2[free] + MOD) % MOD;
      }
    }
    answer as i32
  }
}