0

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?

Improve this question
2
  • Don't assume a problem with LeetCode ;-) Your algorithm is a brute force approach, and not efficient enough to pass all test cases in time. Commented Feb 3, 2022 at 19:55
  • stackoverflow.com/questions/68685440/… Commented Feb 4, 2022 at 12:32

3 Answers 3

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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

Improve this answer

4 Comments

I think this is the right answer or at least one of the right answers (I upvoted). There's an issue with the use of complexity in the leetcode question, because n can only be so big (at most (2^32-1)/3) because above that it's impossible to find input lists where each input number except for one appears 3 times.
@PaulHankin Thank you. In the Leetcode page, I found 1 <= nums.length <= 3 * 10^4. But effectively, from a theoretical point of view, as n is limited by 2^(number of bits)/3, Complexity is O(1) for b fixed. Funny. One possibility is to consider that a number can be repeated 3 times several times... Or we can consider that the real complexity is O(n b) = O(n logn). We can also give to the expression linear complexity a wider sense than O(something).
I think the natural generalization is to allow the range of input numbers to grow as Theta(log n). If you consider arithmetic/logical operations acting on values of size Theta(log n) to be O(1) (the transdichotomous model), you can meet the requirements of the question (O(n) time, O(1) storage) if you're careful about how you compute the sums with bitwise-parallel operations -- this was the motivation of my answer.
The question is unsatisfactory, because doing radix sort on the input and then finding the single item is a viable solution with arguably the right complexities, although I'm pretty sure not the intended solution.
1

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.

Improve this answer

2 Comments

Nice idea, to avoid 32 parallel operations (+1). It seems that the equations can be slightly simplified: temp = (L^x) & ~H; H = x&L | ~x&H; L = temp;.
@Damien I'm sure you're right. If I had more time, I would have written a shorter program!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.