Single Number II Interview Question for Apple

# Single Number II

## Problem 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


## Naive Solution

One approach is to use a hash map to count the occurrences of each number.  We iterate through the array, updating the count for each number in the hash map.  Finally, we iterate through the hash map and return the number with a count of 1.

```python
from collections import Counter

def singleNumber_naive(nums):
    counts = Counter(nums)
    for num, count in counts.items():
        if count == 1:
            return num
    return None  # Or raise an exception, depending on the requirements

Optimal Solution (Bit Manipulation)

We can solve this problem using bit manipulation with constant extra space. The idea is to track the count of each bit position (0 to 31) in the numbers. Since each number (except the single one) appears three times, the count of each bit position will be a multiple of 3, except for the single number. We can use two variables, ones and twos, to track the bits that appear once and twice, respectively.

def singleNumber(nums):
    ones = 0
    twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

Explanation:

ones tracks bits that have appeared once.
twos tracks bits that have appeared twice.
For each number num:
- ones ^ num: If a bit in num is not in ones, it's added to ones. If a bit in num is already in ones, it's removed.
- twos ^ num: If a bit in num is not in twos, it's added to twos. If a bit in num is already in twos, it's removed.
- ones = (ones ^ num) & ~twos: If a bit is in both ones and twos, it means it has appeared three times, so we clear it from ones.
- twos = (twos ^ num) & ~ones: If a bit is in both twos and ones, it means it has appeared three times, so we clear it from twos.

Finally, ones will contain the bits of the single number that appears only once.

Big(O) Runtime Analysis

The optimal solution iterates through the input array nums once. The bitwise operations take constant time. Therefore, the time complexity is O(n), where n is the length of the input array.

Big(O) Space Usage Analysis

The optimal solution uses only two integer variables, ones and twos, regardless of the input size. Therefore, the space complexity is O(1), constant extra space.

Edge Cases

Empty Array: If the input array is empty, the problem statement doesn't explicitly state what to return. In practice, it's best to raise an exception or return a specific value (e.g., None) to indicate an invalid input.
Single Element is Zero: The algorithm should correctly handle the case where the single element that appears once is zero.
Negative Numbers: The algorithm should work correctly with both positive and negative numbers.
Large Input Array: The algorithm's linear time complexity makes it efficient even for large input arrays.

def singleNumber_edge_cases(nums):
    if not nums:
        return None  # Or raise ValueError("Input array cannot be empty")

    ones = 0
    twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

# Example Usage:
print(singleNumber_edge_cases([2, 2, 3, 2]))  # Output: 3
print(singleNumber_edge_cases([0, 1, 0, 1, 0, 1, 99]))  # Output: 99
print(singleNumber_edge_cases([-2, -2, 1, -2])) # Output: 1
print(singleNumber_edge_cases([])) # Output: None