In this Leetcode Find the Duplicate Number problem solution we have 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 uses only constant extra space.

Leetcode Find the Duplicate Number problem solution


Problem solution in Python.

d = dict(collections.Counter(nums))
        print(d)
        for k in d:
            if d[k] > 1:
                return k



Problem solution in Java.

if(nums == null || nums.length == 0) {
            return 0;
        }
        int l = 1, r = nums.length;
        while(l < r){
            int cnt = 0;
            int mid = l + (r-l)/2;
            for(int num : nums) {
                if(num <= mid) cnt++;
            }
            if(cnt <= mid) {
                l = mid+1;
            } else {
                r = mid;
            }
        }
        return l;


Problem solution in C++.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        
        vector<int> map(nums.size(), 0 );
        
        for(int i = 0; i < nums.size(); i++)
        {
            if(++map[nums[i]] > 1)
                return nums[i];
        }
        return 0;
    }
};


Problem solution in C.

int findDuplicate(int* a, int numsSize) {

int i=0;

while(i<numsSize)
{
    while(a[i] != (i+1))
    {
        if(a[a[i]-1] == a[i])
            return a[i];
        else
        {
            //swap a[a[i]-1] and a[i]
            a[a[i]-1] = a[i] + a[a[i]-1] - (a[i] = a[a[i]-1]);
        }
    }
    i++;
}
}