137. Single Number II

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.

 

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

 

Follow up: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Rust Solution

struct Solution;

impl Solution {
    fn single_number(nums: Vec<i32>) -> i32 {
        let mut once = 0;
        let mut twice = 0;
        for x in nums {
            once = !twice & (once ^ x);
            twice = !once & (twice ^ x);
        }
        once
    }
}

#[test]
fn test() {
    let nums = vec![2, 2, 3, 2];
    let res = 3;
    assert_eq!(Solution::single_number(nums), res);
    let nums = vec![0, 1, 0, 1, 0, 1, 99];
    let res = 99;
    assert_eq!(Solution::single_number(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.