137.Single_Number_II(Medium).md

137. Single Number II (Medium)

Date and Time: Feb 13, 2025, 00:02 (EST)

Link: https://leetcode.com/problems/single-number-ii

Question:

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

Edge Case:

Input: nums = [-2,-2,-3,-2]
Output: -3

Constraints:

• 1 <= nums.length <= 3 * 10^4

• -2^31 <= nums[i] <= 2^31 - 1

• Each element in nums appears exactly three times except for one element which appears once.

Walk-through:

For each bit 0 to 31, we count their occurrences with each bit for each num from nums. Then, we update occurrences % 3 (either 1 or 0) and update the corresponding bit for res.

Python Solution:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Calculate each bit's occurrences % 3, update res's corresponding bit
        # Check if res > (1 << 31), means res is negative, handle 2's complement

        # TC: O(n), n=len(nums), SC: O(1)
        res = 0
        # Loop over each bit
        for shift in range(32):
            counts = 0
            # Count bit's occurrences
            for num in nums:
                counts += (num >> shift) & 1
            counts %= 3
            # Update res with the bit position
            res = res | (counts << shift)
        # Check if res is negative, handle 2's complement
        if res >= (1 << 31):
            res -= (1 << 32)
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$