Python O(n) time O(1) space, 9 lines of code, with explanation


  • 1
    P

    We count the sum of each 32 bit respectively for the given array and [1,2,3,...,n]. If at a certain bit, the sum of given array is larger, it means the duplicated number has a '1' at that position.

    class Solution(object):
        def findDuplicate(self, nums):
            ans = 0
            for i in range(0, 32):
                mask = 1 << i
                a = b = 0
                for j in range(len(nums)):
                    a += j & mask
                    b += nums[j] & mask
                ans += (1 if b > a else 0) << i
            return ans
    

  • 0
    L

    Since log n < 32, your solution is not faster than the binary search method. However, you can make your outer loop a while loop and add the termination statement after the inner loop

    if a == 0:
        break
    

    which make it n log n and your algorithm could then be applied to more general case where n is not bounded by 32 bits.


Log in to reply
 

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