05_SingleNumber2.py

# Question link - https://leetcode.com/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Sol3: Most optimal solution - O(n) , O(1)
        # This we are going to use the bucket as twos and ones 
        ones , twos = 0,0

        for num in nums:
            # If not in twos , then first Appear
            ones = (ones ^ num) & ~twos
            # If in ones ,then removes ones and add into twos
            twos = (twos ^ num) & ~ones

        return ones 

        # # Sol2 - O(NlogN) , O(1)
        # # Sortarray and return traverse for middle ele upto 3
        # n = len(nums)
        # # Sort the array
        # nums.sort() 

        # for i in range(1 , n , 3):
        #     if nums[i] != nums[i-1]:
        #         return nums[i-1]
        # # If not found 
        # return nums[n - 1]

        # #sol1 - O(N*32) , O(1)
        # ans = 0
        # for bitIndex in range(32):
        #     count = 0
        #     for num in nums:
        #         # Check for the setbits 1s 
        #         if (num & ( 1 << bitIndex)):
        #             count += 1
        #     # If not multiple of three 
        #     if count % 3 != 0:
        #         ans |= 1 << bitIndex

        # # Handling the negative bits 
        # if ans >= 2**31:
        #     ans -= 2**32

        # return ans