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. You must implement a solution with a linear runtime complexity and use only constant extra space.

For example:

nums = [2,2,3,2] should return 3

nums = [0,1,0,1,0,1,99] should return 99

What algorithm can be used to find the single element in the array? Explain the time and space complexity of your approach. Provide code implementing the algorithm. Are there any edge cases or alternative approaches?

class Solution {
    public int singleNumber(int[] nums) {
        int seenOnce = 0;
        int seenTwice = 0;

        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }

        return seenOnce;
    }
}

Explanation:

The code utilizes bit manipulation to find the single number in an array where every other number appears three times. The algorithm uses two integer variables, seenOnce and seenTwice, to track the appearance of each number.

1. Initialization:

   • seenOnce and seenTwice are initialized to 0.

2. Iteration:

   • For each number num in the array nums, the seenOnce and seenTwice variables are updated using bitwise operations.
   • seenOnce = ~seenTwice & (seenOnce ^ num);
   • seenTwice = ~seenOnce & (seenTwice ^ num);

3. Logic:

   • When a number appears for the first time, it is stored in seenOnce. The XOR operation (^) effectively adds the number to seenOnce.
   • When the same number appears for the second time, it is removed from seenOnce (due to the XOR operation canceling it out) and stored in seenTwice. The ~seenOnce & part ensures this happens only when the number is no longer in seenOnce.
   • When the same number appears for the third time, it is removed from seenTwice. The ~seenTwice & part ensures this happens only when the number is in seenTwice.
   • The variables seenOnce and seenTwice act as counters modulo 3 for each number. If a number appears three times, it effectively cancels itself out in both seenOnce and seenTwice.

4. Result:

   • After iterating through all the numbers, seenOnce will contain the single number that appears only once.

Example:

Consider the input nums = [2, 2, 3, 2]

Final Result: seenOnce = 3

Time Complexity

The time complexity is O(n) because the code iterates through the input array once.

Space Complexity

The space complexity is O(1) because the code only uses a constant amount of extra space, regardless of the size of the input array.