Striver's SDE Sheet Journey - #10 Find the duplicate in an array
Tags: programming, beginners, computerscience, java
Published: 2022-01-01 13:20:32

hi Dev,
today we are going to solve the 10th problem from the sheet, which is **Find the duplicate in an array**.
lets start....


> **<u>Problem Statement</u> :-**

_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._

##  <u>Solution 1</u>
_using sorting, we can easily find the duplicate number by linearly checking the one which has the same at the next position._

**step-1** first sort the array.

**step-2** run a loop from `i=0` to `n`,then
 > if `nums[i] == nums[i+1]`, then return the `nums[i]`

**step-3** end.

## Java
```java
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        
        for(int i=0; i<nums.length;i++){
            if(nums[i] == nums[i+1]) return nums[i];
        }
        
        return 0;
    }
}
```
**Time Complexity :** **O(nlogn)**

**Space Complexity :** **O(1)**

##  <u>Solution 2</u>

_Since we know that. The range of the array’s numbers are from 1 to N. so, we can use the array indices as the visited number._

**step-1** run a loop from `i=0` to `N`, then
 > **1.** get the i'th number from the array as `index`.
 `index = nums[i]`

 > **2.** mark the index value as visited number, by multiply -1
 `nums[abs(index)] *= -1 `

 > **3.** Check, if is already marked, then return the number.
if `nums[abs(index)] > 0`, then return `abs(nums[i])`
`// abs -> absolute function`

**step-2** end.

> Java

```java
class Solution {
    public int findDuplicate(int[] nums) {
        
        
        for(int i=0;i<nums.length;i++){
            int index = Math.abs(nums[i]) - 1;
            
            nums[index] *= -1;
            
            if(nums[index] > 0) return Math.abs(nums[i]);
        }
        
        return 0;
    }
}
```

**Time Complexity :** **O(n)**

**Space Complexity :** **O(1)**


##  <u>Solution 3</u>
_this problem can be solve by using **Binary Search** algorithm_

traverse through the array and count the numbers which are less than or equal to mid .

1. If the count is less than mid, then duplicate number should be greater than mid.

2. If the count is greater than mid, then duplicate number should be less than mid.

3. then narrow down the search space by updating the left & right value.

_for more understanding, read [Pigeonhole Principle](https://en.wikipedia.org/wiki/Pigeonhole_principle#:~:text=In%20mathematics%2C%20the-,pigeonhole,-principle%20states%20that)_
 
lets understand this algo step by step.

**step-1** initialise the variables `left=0 `, `right=arrLen`

**step-2** run a loop if `left < right,` then
 > **1.** initialise `count=0 `

 > **2.** calculate the mid
 `mid = (left + right) / 2`

 > **3.** run a loop from `i=0` to `n` , then count the numbers which are less than `mid`
  > if `nums[i] <= mid`, then `count++`

 > **4.** if `count > mid` then update `right`
  > `right = mid`

 > **5.** if `count < mid` then update `left`
  > `left = mid+1`

**step-3** return the `left` variable.

**step-4** end.

> Java 

```java
class Solution {
    public int findDuplicate(int[] nums) {
        int left=0, right=nums.length-1;
        
        while(left < right){
            int count =0;
            
            int mid = (left + right) / 2;
            
            for(int i=0;i<nums.length;i++)
                if(nums[i] <= mid) count++;
            
            if(count > mid)
                right = mid;
            else
                left = mid+1;
            
        }
        
        return left;
    }
}
```
**Time Complexity :** **O(nlogn)**

**Space Complexity :** **O(1)**

_thank you for reading this article, if you find any mistakes, let me know in the comment section_