My python O(N) time and O(1) space


  • -1
    B
        def findDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            xor=0
            for num in nums:
                newx=xor^(2**num)
                if newx<xor:
                    return num
                else:
                    xor=newx

  • 0

    That's neither O(1) space nor O(N) time (assuming with "N" you mean n).


  • 0
    B

    @ManuelP can you please let me know the bug


  • 0

    @bhanusri95 Surely you know what you're doing? I.e., that you're using n-bit numbers? I can't imagine you wrote that code and don't know that it's doing that.

    And n bits are n bits. Not O(1) space but O(n) space. And their operations also don't just take O(1) time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.