# 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 unique_set.add(num)

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 uniqueValues.add(nums[i]); } } };

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; } }