Code Destine

Problem Statement

You have given an array N, containing n + 1 integer elements, where each integer element is between 1 (inclusive) and n (inclusive). Write a program to return the duplicate integer.

Note: Integer array N contains only one duplicate integer.

Example 

Input :- [6, 5, 4, 1, 3, 2, 3]
Output :- 3

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

Solution – Set

A set’s uniqueness property can be used to solve this problem.

Iterate through the integer array N and at each iteration check if Set contains the current element, if yes then return the element as a result otherwise add the current element to the set.

Program

import java.util.HashSet;
import java.util.Set;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.findDuplicate(new int[] {1, 5, 4, 2, 3, 2});
		System.out.println(result);					
	}
	
	/* Solution */    
	public int findDuplicate(int[] nums) {
        
        Set<Integer> set = new HashSet<>();
        for(int i : nums){
            if(set.contains(i)){
                return i;
            }
            set.add(i);
        }
        return 0;
    }
}

Solution – Floyd’s Cycle Detection Algorithm

The given input array N contains n + 1 integer elements between 1 to n, with only one duplicate integer element. If we use consider index of an array as a node of linked list and it’s value as a next pointer, then this problem can be deduced Linked List Cycle problem. Hence Floyd’s Cycle Detection Algorithm can be used to solve this problem. For more information see here

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int result = main.findDuplicate(new int[] {1, 5, 4, 2, 3, 2});
		System.out.println(result);					
	}
	
	/* Solution */    
	public int findDuplicate(int[] nums) {        
        int slow = nums[0];
        int fast = nums[0];
        do {
        	slow = nums[slow];
        	fast = nums[nums[fast]];
        } while (slow != fast);

        int first = nums[0];
        int second = slow;
        while (first != second) {
            first = nums[first];
            second = nums[second];
        }
        return second;
    }
}

Result

2 

Similar Post

1. Find Common Characters in Array of Strings
2. Duplicate Zeros in Array
3. Find Peak Element in Array

That’s all for Find the Duplicate Number in Array in Java, If you liked it, please share your thoughts in a comments section and share it with others too.