# Leetcode --- 287. Find the Duplicate Number

## [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
### Description:
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

:::warning
There is **only one repeated number** in nums, return this repeated number.

You must solve the problem **without modifying the array nums and uses only constant extra space**.
:::
:::info

:::

**binary search**

**floyd**

### 解法條列
1. Sum of Set Bits解 O(nlogn) O(1)
2. binary search O(nlogn) O(1)
3. 優化解 floyd O(n) O(1)

### 解法細節

:::success
floyd:
:::

### Python Solution

---

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 1
        right = len(nums) - 1
        
        while left <= right:
            temp = (left + right) // 2
            count = 0
            for num in nums:
                if(num <= temp):
                    count += 1
            if count > temp:
                duplicate = temp
                right = temp - 1
            else:
                left = temp + 1
                
        return duplicate

---

floyd解

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[0]
        while(True):
            slow = nums[slow]
            fast = nums[nums[fast]]
            if(slow == fast):
                break
        slow = nums[0]
        while(True):
            if(slow == fast):
                return slow
            slow = nums[slow]
            fast = nums[fast]
            

---

###### tags: `leetcode` `example` `array` `easy` `medium`