137. Single Number II

This problem asks to find the single number that appears only once in an array where all other numbers appear exactly three times. We'll explore several solutions with varying approaches and complexities.

Solution 1: Bitwise Operation (O(n log M) time, O(1) space)

This approach iterates through each bit position (0 to 31 for 32-bit integers). For each bit, it counts how many numbers have a '1' in that bit position. If the count is not divisible by 3, it means the single number has a '1' in that bit position. The final result is constructed by setting bits accordingly.

Time Complexity: O(n log M), where n is the length of the array and M is the maximum value in the array. We iterate through each number (n) and each bit (log M).

Space Complexity: O(1), as we only use a constant number of variables.

Python Code:

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:
                ans |= 1 << i  #Set the bit if count %3 != 0
        return ans
 

Java Code:

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;
            }
            if (cnt % 3 != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

Similar code can be implemented in other languages (C++, Go, JavaScript, TypeScript, Rust, C, Swift) following the same bit manipulation logic. The core idea remains consistent across languages.

Solution 2: Digital Circuit (O(n) time, O(1) space)

This solution uses two integer variables, a and b, to track the counts modulo 3. It cleverly uses bitwise operations to simulate a finite state machine that keeps track of the counts.

Time Complexity: O(n), as we iterate through the array once.

Space Complexity: O(1), constant extra space.

Python Code:

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

Java Code:

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;
    }
}

Again, this approach can be implemented in other languages with similar efficiency.

Solution 3: Set + Math (O(n) time, O(n) space)

This solution uses a set to find unique numbers, sums them, and then uses the fact that the sum of all numbers (with duplicates) minus three times the sum of unique numbers, all divided by 2, will give the single number.

Time Complexity: O(n) due to set creation and sum operations.

Space Complexity: O(n) due to the set storing unique numbers. This solution is less efficient in space than the previous two.

TypeScript Code:

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;
}

JavaScript Code:

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 (Optimized, O(n) time, O(1) space)

This solution uses a more concise bit manipulation approach. It maintains two variables ans and acc to cleverly track the single number.

Time Complexity: O(n) - Single pass through the array.

Space Complexity: O(1) - Constant extra space.

TypeScript Code:

function singleNumber(nums: number[]): number {
    let [ans, acc] = [0, 0];
    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }
    return ans;
}
 

JavaScript Code:

function singleNumber(nums) {
    let [ans, acc] = [0, 0];
    for (const x of nums) {
        ans ^= x & ~acc;
        acc ^= x & ~ans;
    }
    return ans;
}

Recommendation: Solutions 2 and 4 are the most efficient in terms of both time and space complexity. Solution 1 is a good alternative if you're more comfortable with simpler bit manipulation. Solution 3 is less space-efficient and should be avoided unless space is not a major concern.