Single Number I and II

137.Single Number II

Bit Manipulation

Array

Problem Statement:

Given an integer array nums where every element appears three times except for one element which appears once. Find the single element. For Single Number I, elements appear twice except for one element.

Example:

Input:

nums = [2,2,3,2]

→

Output:

3

Algorithm:

1. Single Number II: - Count set bits at each position - If count % 3 ≠ 0, bit is from single number - Build result using OR operation
2. Single Number I: - Use XOR property: x^x = 0 - Elements appearing twice cancel out - Result is the single element

Complexity:

Single Number II: Time O(32*n), Space O(1) | Single Number I: Time O(n), Space O(1)

Java Solution:

// Solution for Single Number II (elements appear three times)
public int singleNumber(int[] nums) {
    // Final result
    int res = 0;
    
    // Check each bit position (32-bit integer)
    for (int i = 0; i < 32; i++) {
        // Count number of set bits at position i
        int sum = 0;
        // Create mask for current bit position
        int mask = 1 << i;
        
        // Count set bits for all numbers at position i
        for (int n : nums) 
            if ((n & mask) != 0) 
                sum++;
        
        // If sum not divisible by 3, bit belongs to single number
        if (sum % 3 != 0)
            res |= mask;
    }
    return res;   
}

// Solution for Single Number I (elements appear twice)
public int singleNumberII(int[] nums) {
    // Use XOR to cancel out pairs
    int res = 0;
    
    // XOR all numbers - pairs cancel out (x^x = 0)
    for (int num : nums) 
        res ^= num;
        
    return res;
}

Python Solution:

def singleNumber(self, nums: List[int]) -> int:
    # Final result
    res = 0
    
    # Check each bit position (32-bit integer)
    for i in range(32):
        # Count set bits at position i
        bit_sum = 0
        mask = 1 << i
        
        for num in nums:
            if num & mask:
                bit_sum += 1
        
        # If sum not divisible by 3, bit belongs to result
        if bit_sum % 3:
            res |= mask
            
    # Handle negative numbers in Python
    return res - (1 << 32) if res >= (1 << 31) else res

# Solution for Single Number I
def singleNumberII(self, nums: List[int]) -> int:
    # XOR all numbers - pairs cancel out
    return reduce(lambda x, y: x ^ y, nums)

C++ Solution:

int singleNumber(vector<int>& nums) {
    // Final result
    int res = 0;
    
    // Check each bit position
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        int mask = 1 << i;
        
        // Count set bits at position i
        for (int num : nums) 
            if (num & mask)
                sum++;
                
        if (sum % 3)
            res |= mask;
    }
    
    return res;
}

// Solution for Single Number I
int singleNumberII(vector<int>& nums) {
    // XOR all numbers to cancel pairs
    return accumulate(nums.begin(), nums.end(), 
        0, [](int a, int b) { return a ^ b; });
}