137. Single Number II

Description

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.

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 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Solutions

Solution 1: Bitwise Operation

Thinking

Numbers appear three times except one; XOR is no longer enough because \(x\oplus x\oplus x=x\). The follow-up still wants constant space. Count \(1\)s per bit modulo \(3\): bits from the triples vanish, and the remainder is the answer. The sign bit is handled separately to avoid overflow.

We can enumerate each binary bit \(i\), and for each binary bit, we calculate the sum of all numbers on that bit. If the sum of the numbers on that bit can be divided by 3, then the number that only appears once on that bit is 0, otherwise it is 1.

The time complexity is \(O(n \times \log M)\), where \(n\) and \(M\) are the length of the array and the range of elements in the array, respectively. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScriptRustCSwift

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cnt = sum(num >> i & 1 for num in nums)
            if cnt % 3:
                if i == 31:
                    ans -= 1 << i
                else:
                    ans |= 1 << i
        return ans

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += num >> i & 1;
            }
            cnt %= 3;
            ans |= cnt << i;
        }
        return ans;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (int num : nums) {
                cnt += ((num >> i) & 1);
            }
            cnt %= 3;
            ans |= cnt << i;
        }
        return ans;
    }
};

func singleNumber(nums []int) int {
    ans := int32(0)
    for i := 0; i < 32; i++ {
        cnt := int32(0)
        for _, num := range nums {
            cnt += int32(num) >> i & 1
        }
        cnt %= 3
        ans |= cnt << i
    }
    return int(ans)
}

function singleNumber(nums: number[]): number {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        const count = nums.reduce((r, v) => r + ((v >> i) & 1), 0);
        ans |= (count % 3) << i;
    }
    return ans;
}

function singleNumber(nums) {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        const count = nums.reduce((r, v) => r + ((v >> i) & 1), 0);
        ans |= (count % 3) << i;
    }
    return ans;
}

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        for i in 0..32 {
            let count = nums.iter().map(|v| (v >> i) & 1).sum::<i32>();
            ans |= count % 3 << i;
        }
        ans
    }
}

int singleNumber(int* nums, int numsSize) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int count = 0;
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] >> i & 1) {
                count++;
            }
        }
        ans |= (uint) (count % 3) << i;
    }
    return ans;
}

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var a = nums.sorted()
        var n = a.count
        for i in stride(from: 0, through: n - 2, by: 3) {
            if a[i] != a[i + 1] {
                return a[i]
            }
        }
        return a[n - 1]
    }
}

Solution 2: Digital Circuit

Thinking

Solution 1 rescans the array for every bit. Two integers \(a,b\) store each bit's count modulo \(3\); a truth table updates them as each number arrives, so one pass does the same counting.

We can use a more efficient method that uses digital circuits to simulate the above bitwise operation.

Each binary bit of an integer can only represent 2 states, 0 or 1. However, we need to represent the sum of the \(i\)-th bit of all integers traversed so far modulo 3. Therefore, we can use two integers \(a\) and \(b\) to represent it. There are three possible cases:

The \(i\)-th bit of integer \(a\) is 0 and the \(i\)-th bit of integer \(b\) is 0, which means the modulo 3 result is 0;
The \(i\)-th bit of integer \(a\) is 0 and the \(i\)-th bit of integer \(b\) is 1, which means the modulo 3 result is 1;
The \(i\)-th bit of integer \(a\) is 1 and the \(i\)-th bit of integer \(b\) is 0, which means the modulo 3 result is 2.

We use integer \(c\) to represent the number to be read in, and the truth table is as follows:

\(a_i\)	\(b_i\)	\(c_i\)	New \(a_i\)	New \(b_i\)
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	0

Based on the truth table, we can write the logical expression:

\[ a_i = a_i' b_i c_i + a_i b_i' c_i' \]

and:

\[ b_i = a_i' b_i' c_i + a_i' b_i c_i' = a_i' (b_i \oplus c_i) \]

The final result is \(b\), because when the binary bit of \(b\) is 1, it means that the number appears only once.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScriptRust

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = b = 0
        for c in nums:
            aa = (~a & b & c) | (a & ~b & ~c)
            bb = ~a & (b ^ c)
            a, b = aa, bb
        return b

class Solution {
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        for (int c : nums) {
            int aa = (~a & b & c) | (a & ~b & ~c);
            int bb = ~a & (b ^ c);
            a = aa;
            b = bb;
        }
        return b;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int c : nums) {
            int aa = (~a & b & c) | (a & ~b & ~c);
            int bb = ~a & (b ^ c);
            a = aa;
            b = bb;
        }
        return b;
    }
};

func singleNumber(nums []int) int {
    a, b := 0, 0
    for _, c := range nums {
        aa := (^a & b & c) | (a & ^b & ^c)
        bb := ^a & (b ^ c)
        a, b = aa, bb
    }
    return b
}

function singleNumber(nums: number[]): number {
    let a = 0;
    let b = 0;
    for (const c of nums) {
        const aa = (~a & b & c) | (a & ~b & ~c);
        const bb = ~a & (b ^ c);
        a = aa;
        b = bb;
    }
    return b;
}

function singleNumber(nums) {
    let a = 0;
    let b = 0;
    for (const c of nums) {
        const aa = (~a & b & c) | (a & ~b & ~c);
        const bb = ~a & (b ^ c);
        a = aa;
        b = bb;
    }
    return b;
}

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut a = 0;
        let mut b = 0;

        for c in nums {
            let aa = (!a & b & c) | (a & !b & !c);
            let bb = !a & (b ^ c);
            a = aa;
            b = bb;
        }

        return b;
    }
}

Solution 3: Set + Math

Thinking

If extra space is allowed, the unique value is \((3\sum_{\mathrm{unique}}-\sum_{\mathrm{all}})/2\). Deduplicate, sum twice, and divide. Direct, but \(O(n)\) space.

TypeScriptJavaScript

function singleNumber(nums: number[]): number {
    const sumOfUnique = [...new Set(nums)].reduce((a, b) => a + b, 0);
    const sum = nums.reduce((a, b) => a + b, 0);
    return (sumOfUnique * 3 - sum) / 2;
}

function singleNumber(nums) {
    const sumOfUnique = [...new Set(nums)].reduce((a, b) => a + b, 0);
    const sum = nums.reduce((a, b) => a + b, 0);
    return (sumOfUnique * 3 - sum) / 2;
}

Solution 4: Bit Manipulation

Thinking

The Solution 2 state machine collapses to two masks: \(\textit{ans}\) and \(\textit{acc}\) hold bits seen once and twice. They stay disjoint as \(x\) arrives; \(\textit{ans}\) is the number that appeared once. Shorter code.

TypeScriptJavaScript

function singleNumber(nums: number[]): number {
    let [ans, acc] = [0, 0];

    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }

    return ans;
}

function singleNumber(nums) {
    let [ans, acc] = [0, 0];

    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }

    return ans;
}

137. Single Number II

Description

Solutions

Solution 1: Bitwise Operation

Solution 2: Digital Circuit

Solution 3: Set + Math

Solution 4: Bit Manipulation

Comments