#137
Medium Algorithms Single number ii
Array Bit Manipulation
66.7% acceptance
Jan 12, 2026
8634
750
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Solution
Rust
Time O(n)
Space O(1)
impl Solution {
pub fn single_number_ii(nums: Vec<i32>) -> i32 {
// Using bit manipulation: count bits at each position
let mut ones = 0;
let mut twos = 0;
for &num in &nums {
// Add num to ones if it's not in twos
ones = (ones ^ num) & !twos;
// Add num to twos if it's already in ones
twos = (twos ^ num) & !ones;
}
ones
}
}