CODEWITHSUNDEEP
pythonalgorithm
Noble Eugene
Noble Eugene

Reputation: 737

Getting time limit exceeded in leetcode

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?

Upvotes: 0

Views: 1087

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58271

The similar problem where each number appears twice and the solution appears once has a solution that XORs all the inputs together. The duplicate numbers cancel out, leaving the solution.

XOR can be thought of as element-wise addition modulo 2, where the input numbers are treated as a vector of bits (0 or 1).

When the non-solutions appear three times each, one can use a similar approach but modulo 3. Treat the input numbers as a vector of bits, and add those vectors element-wise modulo 3.

It's possible to do this summation using bitwise operations. When you add modulo 3, you can get the values 0, 1, 2, so you need at least 2 bits per position. An efficient way to do this uses two variables (HI and LO) where the count of the bits in position i is spread between the i'th bit of HI and the i'th bit of LO. Python code for this can be written like this:

def single(xs):
    HI, LO = 0, 0
    for x in xs:
        HI, LO = (LO&x)|(HI&~(LO&x)), (LO&~x)|(~LO&x)
        HI, LO = HI&~(HI&LO), LO&~(HI&LO)
    return LO

This code uses two variables so is arguably O(1) space, and performs O(n) bitwise operations.

Upvotes: 1

Damien
Damien

Reputation: 4864

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).

Upvotes: 1

oflint_
oflint_

Reputation: 297

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.

Upvotes: 4

Related Questions