Longest strictly increasing subsequence with non zero bitwise and

Array Binary Search Bit Manipulation Enumeration

50.6% acceptance

Mar 16, 2026

101

Return length of longest strictly increasing subsequence with non-zero AND. If no such subsequence exists, return 0.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subsequence(nums: Vec<i32>) -> i32 {
    // For the AND to be non-zero, at least one bit must be set in ALL elements of the subsequence.
    // For each bit position b (0..30), find the longest strictly increasing subsequence
    // among elements that have bit b set. Use standard LIS with binary search (O(n log n)).
    let mut ans = 0;
    for bit in 0..30 {
      let mask = 1 << bit;
      // Collect elements with this bit set (preserving order), skip 0
      let filtered: Vec<i32> = nums.iter().filter(|&&x| x & mask != 0).copied().collect();
      if filtered.is_empty() { continue; }
      // Standard LIS
      let mut tails: Vec<i32> = Vec::new();
      for &x in &filtered {
        let pos = tails.partition_point(|&t| t < x);
        if pos == tails.len() {
          tails.push(x);
        } else {
          tails[pos] = x;
        }
      }
      ans = ans.max(tails.len());
    }
    ans as i32
  }
}