Once twice

Array Bit Manipulation

75.9% acceptance

Mar 31, 2026

You are given an integer array nums. In this array: Exactly one element appears once. Exactly one element appears twice. All other elements appear exactly three times. Return an integer array of length 2, where the first element is the one that appears once, and the second is the one that appears twice. Your solution must run in O(n) time and O(1) space.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn once_twice(nums: Vec<i32>) -> Vec<i32> {
    // O(n) time, O(1) space using mod-3 bit counting + partitioning.
    // Standard sequential mod-3 counter: ones then twos (twos uses NEW ones).
    let mut ones: i32 = 0;
    let mut twos: i32 = 0;
    
    for &x in &nums {
      ones = (ones ^ x) & !twos;
      twos = (twos ^ x) & !ones; // uses updated ones
    }
    
    // ones = a & !b (bits of once-element not in twice-element)
    // twos = b & !a (bits of twice-element not in once-element)
    // a XOR b = ones ^ twos (they are distinct, so this is non-zero)
    
    let axb = ones ^ twos;
    let diff_bit = axb & axb.wrapping_neg(); // lowest set bit
    
    // Partition nums by diff_bit, run mod-3 counter on each partition.
    let mut o1: i32 = 0;
    let mut t1: i32 = 0;
    let mut o2: i32 = 0;
    let mut t2: i32 = 0;
    
    for &x in &nums {
      if x & diff_bit != 0 {
        o1 = (o1 ^ x) & !t1;
        t1 = (t1 ^ x) & !o1;
      } else {
        o2 = (o2 ^ x) & !t2;
        t2 = (t2 ^ x) & !o2;
      }
    }
    
    // In the partition containing a (once-element): o_partition = a
    // In the partition containing b (twice-element): t_partition = b
    if ones & diff_bit != 0 {
      // a is in partition 1 (has diff_bit set)
      vec![o1, t2]
    } else {
      // b is in partition 1
      vec![o2, t1]
    }
  }
}