Simple 5 line Python solution using binary search

• The idea is that if you have a number (e.g. 5) and there are 5 numbers in the array that are less than or equal to 5 then the duplicate has to be a number greater than 5. Otherwise, by the pigeonhole principle the duplicate has to be one of the numbers between 1 and 5 inclusive.

``````class Solution(object):
def findDuplicate(self, nums):
left, right = 1, len(nums)-1
while left < right:
mid = (right + left)/2
left, right = [left, mid] if sum(i <= mid for i in nums) > mid else [mid+1, right]
return right``````

• Haha! You beat me to it! :)

• but,your program has a serious defection,For example: when the test case is =[1, 2, 3, 4, 5, 6, 7, 7 , 8, 9]

• ``````class Solution(object):
def findDuplicate(self, nums):
left, right = 1, len(nums) - 1
while left < right:
mid = (right + left) / 2
left, right = [left, mid] if sum(i <= mid for i in nums) > mid else [mid + 1, right]
return right

nums = [1, 2, 3, 4, 5, 6, 7, 7 , 8, 9]
my = Solution()
print(my.findDuplicate(nums))
``````

• Is it possible you are using Python 3 for your test? In that case the single '/' represents floating point division rather than integer division as in Python 2.

• Is it possible you are using Python 3 for your test? In that case the single '/' represents floating point division rather than integer division as in Python 2.

• Does the problem assume that the array is in increasing order? What if it's not?

• it doe NOT assume the arry is in increasing order. the key thing to notice here is that even though the correct mid number between 1-n is done through binary search, the actual counting process goes through the entire range each time which is why the solution is log(n) * n (for each counting process)

• it is so hard to come up with this idea

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