Find the Duplicate Number

author: Sergei Golitsyn
link: 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.

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.

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

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

Solution:

Ok ok, hello everyone. Let's try to solve this problem.
We know that we have elements from 1 to n.
And all this elements were sorted.
What if
we will check the middle element and calculate count of elements less that the middle
If count less than middle element, that means that that we have duplicate element in the right part.

For example:

[1,2,3,4,5,5,6]
mid = 4
foreach(1 : 6) --> 
if (num <= cur){
 count ++;
}
count = 1 (1)
...
count = 4 (4)

And we have count as 4, that is why we have to move into right part. Is it clear?

Then in the right part we can do the same. And move to the right or to the left part.

Finally in the left part we set result as middle element, because otherwise we move to another side.

And yes, it is a modified binary search. You seem simple algorithm for complicated problem.

Sure you can iterate over array, and it would take O(N) time. In this approach we have O(log(N)) time complexity without additional memory.

Full code below:

    public int findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length - 1;

        int rez = -1;

        while(start <= end){
            int cur = (end + start) / 2;

            int count = 0;
            for (int num : nums){
                if (num <= cur){
                    count ++;
                }
            }
            if (count > cur){
                rez = cur;
                end = cur - 1;
            } else {
                start = cur + 1;
            }

        }
        return rez;
    }