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