# Find the Duplicate Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-duplicate-number)
Canonical: https://scaleengineer.com/dsa/problems/find-the-duplicate-number
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nvidia](https://scaleengineer.com/companies/nvidia), [Zoho](https://scaleengineer.com/companies/zoho), [Citadel](https://scaleengineer.com/companies/citadel), [Niantic](https://scaleengineer.com/companies/niantic), [Anduril](https://scaleengineer.com/companies/anduril)
---
## Problem
Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive.

There is only **one repeated number** in `nums`, return _this repeated number_.

You must solve the problem **without** modifying the array `nums` and using only constant extra space.

**Example 1:**

**Input:** nums = [1,3,4,2,2]
**Output:** 2

**Example 2:**

**Input:** nums = [3,1,3,4,2]
**Output:** 3

**Example 3:**

**Input:** nums = [3,3,3,3,3]
**Output:** 3

**Constraints:**

* `1 <= n <= 105`
* `nums.length == n + 1`
* `1 <= nums[i] <= n`
* All the integers in `nums` appear only **once** except for **precisely one integer** which appears **two or more** times.

**Follow up:**

* How can we prove that at least one duplicate number must exist in `nums`?
* Can you solve the problem in linear runtime complexity?

# Approaches
## Brute Force - Nested Loop
Compare each element with every other element in the array to find the duplicate number.
**Time:** O(n²) - where n is the length of the array as we use two nested loops · **Space:** O(1) - only using constant extra space
**Pros:** Simple to understand and implement; No extra space required; No modification to original array
**Cons:** Very inefficient for large arrays; Time complexity is quadratic
### Explanation
This approach involves using two nested loops to compare each element with every other element in the array. When we find two elements that are equal, we return that number as the duplicate.

```java
public int findDuplicate(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}
```
### Algorithm
1. Iterate through the array with index i from 0 to n-1
2. For each i, iterate through the array with index j from i+1 to n-1
3. If nums[i] equals nums[j], return nums[i]
4. If no duplicate is found, return -1

## Sorting Approach
Sort the array first and then check adjacent elements for duplicates.
**Time:** O(n log n) - due to the sorting operation · **Space:** O(n) - need extra space for the sorted copy of the array
**Pros:** Relatively simple to implement; No modification to original array
**Cons:** Not optimal time complexity; Requires extra space; Doesn't meet the constant space requirement
### Explanation
This approach first sorts the array (creating a copy to not modify the original) and then checks adjacent elements to find the duplicate. When two adjacent elements are equal, we've found our duplicate.

```java
public int findDuplicate(int[] nums) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i] == sorted[i-1]) {
            return sorted[i];
        }
    }
    return -1;
}
```
### Algorithm
1. Create a copy of the input array
2. Sort the copied array
3. Iterate through the sorted array
4. Check if current element equals previous element
5. If equal, return the element

## Floyd's Cycle Detection (Tortoise and Hare)
Treat array elements as pointers to indices and use Floyd's cycle detection algorithm to find the duplicate.
**Time:** O(n) - where n is the length of the array · **Space:** O(1) - only using two pointers
**Pros:** Optimal time complexity; Constant space complexity; No modification to original array; Meets all problem constraints
**Cons:** More complex to understand; Requires understanding of cycle detection concept
### Explanation
This approach uses Floyd's Cycle Detection algorithm. Since the numbers are in range [1,n] and there's a duplicate, we can treat array values as pointers forming a linked list, which will have a cycle. The duplicate number is the entry point of the cycle.

```java
public int findDuplicate(int[] nums) {
    // Find the intersection point of the two pointers
    int tortoise = nums[0];
    int hare = nums[0];
    
    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    } while (tortoise != hare);
    
    // Find the entrance to the cycle
    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }
    
    return hare;
}
```
### Algorithm
1. Initialize two pointers (tortoise and hare) at the start
2. Move tortoise one step and hare two steps until they meet
3. Reset tortoise to start
4. Move both pointers one step until they meet again
5. Return the meeting point as the duplicate

# Solutions
### Java

```java
class Solution {
public
  int findDuplicate(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      int cnt = 0;
      for (int v : nums) {
        if (v <= mid) {
          ++cnt;
        }
      }
      if (cnt > mid) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var findDuplicate =
  function (nums) {
    let l = 0;
    let r = nums.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      let cnt = 0;
      for (const v of nums) {
        if (v <= mid) {
          ++cnt;
        }
      }
      if (cnt > mid) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };

```

### CPP

```cpp
class Solution {
public:
  int findDuplicate(vector<int> &nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      int cnt = 0;
      for (int &v : nums) {
        cnt += v <= mid;
      }
      if (cnt > mid) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def findDuplicate(self, nums: List[int]) -> int: def f(x: int) -> bool: return sum(v <= x for v in nums) > x return bisect_left(range(len(nums)), True, key=f)

```