Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once.

METHOD 1:

 class Solution {
    public int findDuplicate(int[] nums) {
        ArrayList<Integer>list = new ArrayList<Integer>();
       
        for(int num:nums){
            if(list.contains(num)){
                return num;
            }
            else{
                list.add(num);
            }
        }
        return -1;
    }
}

Try it on Leetcode

Here, we are doing with ArrayList. If you try to solve using Brute Force then it will end up with TLE(Time Limit Exceeded).

If any number is already present in list, then return that number.  If number is not found in list, then add number to the list.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

Click Follow button to receive updates from us instantly.

Please let us know about your views in comment section.

                                                     😍..Happy Coding...😍