Sergei Golitsyn

Posted on

# Find the Duplicate Number

author: Sergei Golitsyn

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

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course.