# Solution For Find The Duplicate Number

The problem “Find The Duplicate Number” on LeetCode asks us to find the duplicate number in an array of n+1 integers where each integer is between 1 and n (inclusive).

The naive solution to this problem would be to use a nested loop and compare each element with every other element in the array. For an array of size n+1, this solution would have a time complexity of O(n^2). However, this solution is not practical for larger arrays.

A better solution is to use the pigeonhole principle and binary search. We know that there are n integers between 1 and n (inclusive), so at least one integer must be repeated. We can divide the array into two halves, with one half containing the numbers 1 to n/2 and the other half containing the numbers n/2 + 1 to n.

If the number of integers in the first half of the array is greater than n/2, then there must be a duplicate in that half of the array. Otherwise, there must be a duplicate in the second half of the array. We can repeat this process recursively until we find the duplicate.

To implement this solution, we can use a modified binary search algorithm. Initially, we set the lower and upper bounds to 1 and n, respectively. We then calculate the mid-point of the bounds. We count the number of integers in the array that are less than or equal to the mid-point value. If the number of integers is greater than the mid-point value (i.e. there are more integers in the first half of the array), we set the upper bound to the mid-point value. Otherwise, we set the lower bound to the mid-point value + 1. We repeat this process until we find the duplicate.

Here is the Python code implementation of the above algorithm:

def findDuplicate(nums):
“””
:type nums: List[int] :rtype: int
“””
n = len(nums) – 1
left, right = 1, n
while left < right:
mid = (left + right) // 2
count = sum(num <= mid for num in nums)
if count > mid:
right = mid
else:
left = mid + 1
return left

The time complexity of this algorithm is O(n log n) and the space complexity is O(1).

## Step by Step Implementation For Find The Duplicate Number

```public int findDuplicate(int[] nums) {

// edge case
if (nums == null || nums.length == 0) {
return -1;
}

// initialize low and high pointers
int low = 1;
int high = nums.length - 1;

// keep iterating until low and high pointers meet
while (low <= high) {

// find the middle element
int mid = low + (high - low) / 2;

// initialize a counter to keep track of how many elements are less than or equal to the middle element
int count = 0;

// iterate through the array and count how many elements are less than or equal to the middle element
for (int num : nums) {
if (num <= mid) {
count++;
}
}

// if the count is greater than the middle element, that means there are duplicate elements in the range [low, mid]
// so we set high = mid
if (count > mid) {
high = mid;
}

// otherwise, there are duplicate elements in the range [mid + 1, high]
// so we set low = mid + 1
else {
low = mid + 1;
}
}

// at this point, low and high pointers have converged and we have found the duplicate element
return low;
}```
```class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# initialize a set to store unique elements
unique_set = set()

# loop through the list
for num in nums:
# if the element is already in the set, return it
if num in unique_set:
return num
# otherwise, add it to the set
```var findDuplicate = function(nums) {
// create a set to store unique values
let uniqueValues = new Set();

// iterate through the array
for (let i = 0; i < nums.length; i++) {
// if the current value is in the set, return it
if (uniqueValues.has(nums[i])) {
return nums[i];
} else { // otherwise, add it to the set
}
}
};```
```class Solution {
public:
int findDuplicate(vector& nums) {
int n = nums.size();
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};```
```using System;

public class Solution {
public int FindDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];

//Find the intersection point of the two runners.
do
{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);

//Find the "entrance" to the cycle.
int ptr1 = nums[0];
int ptr2 = slow;
while(ptr1 != ptr2)
{
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}

return ptr1;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]