Im trying to solve the single number problem on leetcode. Problem Link

The problem gives a list where each value in the list appears three times except one value that appears only once. We should return this single occuring value.... And ive come up with the following solution in python (Ive only been learning python for a day now)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for x in nums:
            temp = []
            for y in range(len(nums)):
                if(x == nums[y]):
                    temp.append(1)
                if(y == (len(nums)-1)):
                    if(len(temp) == 1):
                        return x
                    else:
                        temp = []

It is correctly solving the test cases but when i try to submit i get a "Time limit exceeded". Is there a way to fix my time complexity in this code or is this a problem from leetcode?

CodePudding user response：

This is a problem with your time complexity. In the leetcode question, it asks for:

You must implement a solution with a linear runtime complexity and use only constant extra space.

Your answer has time complexity n^2 because of your nested for loops. Try to implement your solution only using one for loop to obtain linear runtime complexity.

CodePudding user response：

Each number can hold in a 32 bit word.

For each of the 32 positions, calculate the sum modulo 3. The result correspond to the bit answer value at this position.

Complexity is O(32n) = O(n), linear.

Extra space is O(1).