Single Number Ii - Leetcode Solution

Problem Statement:

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.

Example 1: Input: nums = [2,2,3,2] Output: 3

Example 2: Input: nums = [0,1,0,1,0,1,99] Output: 99

Approach:

The problem can be solved using bit manipulation. Whenever you have to count the occurrence of any number, bitwise AND operation can be useful. Whenever we bitwise AND any two same numbers, we get the same number as a result. If we do a bitwise AND operation between two unique numbers, we will always get 0. We can use this fact to find the single number.

For each i in the 32 bits of the number, we count the number of 1s in the ith position for all the n numbers. If we have a group of 3 numbers, then the number of 1s in the ith position will be 3x or 3x+1, where x is an integer. The single number will have a 1 in the ith position only if the total number of 1s in the ith position is not a multiple of 3.

We can use two variables, ones and twos to keep track of the count of 1s in the ith position. Ones will be used to store the number of 1s in the ith position for which we have not seen a triplet yet. Twos will be used to store the number of 1s in the ith position for which we have seen a triplet.

Algorithm:

1. We initialize ones and twos as 0.
2. For each num in nums, we do the following: a. We update ones and twos as follows:
   • ones = ones XOR num & ~twos
   • twos = twos XOR num & ~ones
3. We return ones, as it will have the single number.

Code in Python:

class Solution: def singleNumber(self, nums: List[int]) -> int: ones = twos = 0 for num in nums: ones = ones ^ num & ~twos twos = twos ^ num & ~ones return ones

Time Complexity:

The time complexity of the algorithm is O(n), where n is the size of the array. We iterate over all the numbers in the array only once.

Space Complexity:

The space complexity of the algorithm is O(1), as we are using only two variables to keep track of the count of 1s in the ith position.

1