1. Find Duplicate Number

Topic :

arrays

Difficulty :

medium

Problem Link :

link

problem statement

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

Approach 1: Using Sorting

Start with the given array of integers.
Sort the array in ascending order using Arrays.sort(nums).
Iterate through the sorted array and check for consecutive equal elements.
If an equal pair is found, return the duplicate number.
If no duplicate is found, return -1.

Time Complexity: O(NlogN+N)

Space Complexity: O(1)

import java.io.*;
import java.util.*;
class FindDuplicateNumber
{
    public static void main(String args[]){
        int nums[]={3,1,3,4,2};
        int res=findDuplicate(nums);
        System.out.println("Duplicate Number: "+res);
    }

    public static int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1])
                return nums[i];
        }
        return -1;
    }
}

Approach 2: Using Hashing

Start with the given array of integers.
Create a boolean array checkIfPresent to keep track of whether each number has been encountered.
Iterate through the array and for each number:
- If the number is not encountered yet, mark it as encountered by setting the corresponding index in checkIfPresent to true.
- If the number is already encountered, return it as the duplicate.

4. If no duplicate is found, return

Time Complexity: O(N)

Space Complexity: O(N)

import java.io.*;
import java.util.*;
class FindDuplicateNumber_Hashing
{
    public static void main(String args[]){
        int nums[]={3,1,3,4,2};
        int res=findDuplicate(nums);
        System.out.println("Duplicate Number: "+res);
    }

    public static int findDuplicate(int[] nums) {
        boolean checkIfPresent[]=new boolean[nums.length+1];
        for (int currentNum : nums){
            if(!checkIfPresent[currentNum])
                checkIfPresent[currentNum]=true;
            else return currentNum;
        }
        return -1;
    }
}

Approach 3: Hare and Tortoise method

Initialize two pointers, slow and fast, both pointing to the first element of the array.
Use Floyd's Tortoise and Hare algorithm to detect a cycle in the array. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
Once the pointers meet (indicating the presence of a cycle), reset the slow pointer to the beginning of the array and move both pointers one step at a time until they meet again. The meeting point is the entrance to the cycle, which corresponds to the duplicate number.
Return the duplicate number found at the entrance to the cycle.

Time Complexity: O(N)

Space Complexity: O(1)

import java.io.*;
import java.util.*;
class FindDuplicate_HareAndTortoise
{
    public static void main(String args[]){
        int nums[]={3,1,3,4,2};
        int res=findDuplicate(nums);
        System.out.println("Duplicate Number: "+res);
    }

    public static int findDuplicate(int[] nums) {
        int slow=nums[0];
        int fast=nums[0];
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        while(slow!=fast);
        slow=nums[0];
        while(fast!=slow){
            fast=nums[fast];
            slow=nums[slow];
        }
        return fast;
    }
}