CC-5 : Find duplicated integer and missing integer in array of integers from 1 to n.

Description:

Given an input array of integers arr from 1 to n where one of the integers is duplicated and one integer is missing, find and return the duplicated and the missing integer.

Test cases and expected outputs:

Input Parameters	Expected outputs
intArray = {1,2,4,4,5} n=5;	Missing number: 3 Duplicate number: 4
intArray = {1,2,3,4,5,5} n=6;	Missing number: 6 Duplicate number: 5
intArray = {1,4,3,4} n=4;	Missing number: 2 Duplicate number: 4

Pseudocode:

The java method should accept following input parameters: arr (integer array) and integer n (the bound n of array from 1 to n).

Initialize a variable hMap of type HashMap to hold the integers from arr and their frequencies.

Iterate through arr using a for loop with idx as a loop variable with initial value 0 and increment idx till it reaches arr.length-1:

If hMap does not contain key arr[idx], then put key-value pair arr[idx] and 0 to hMap.

If hMap contains key arr[idx] with value freq, then put key-value pair arr[idx] and freq+1 to hMap.

After completion of above loop, hMap contains keys that are integers from arr and values corresponding to each key is the frequency of that integer in arr.

Initialize an integer array retVal of size 2 to hold the identified duplicate and missing integer.

Iterate integers using a for loop with loop variable idx starting from 1 and increment idx by 1 till idx is <= n:

If hMap does not contain idx as a key, we have found the missing integer, so set retVal[0] to idx.

If hMap contains idx as a key, and if value corresponding to key idx is 2, we have found the duplicate integer, so set retVal[1] to idx.

After completion of above loop, retVal contains the missing and duplicate integer. Return retVal.

Code:

public int[] hashMapSetMismatch(int[] arr, int n) throws Exception{
	HashMap< Integer,Integer> hMap=new HashMap<Integer, Integer>();
	for (int idx=0; idx < arr.length; idx++) {
		if (hMap.containsKey(arr[idx])){
			int freq=hMap.get(arr[idx]);
			hMap.put(arr[idx], ++freq);
		}else {
			hMap.put(arr[idx], 1);
		}			
	}
	int[] retVal=new int[2];
	for (int idx=1; idx <= n; idx++) {
		if (hMap.getOrDefault(idx,0)==0) {
			retVal[0]=idx;
		}
		if (hMap.getOrDefault(idx,0)==2) {
			retVal[1]=idx;
		}
	}
	return retVal;		
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashMap;


public class HashMapSetMismatch {
	
public int[] hashMapSetMismatch(int[] arr, int n) throws Exception{
	HashMap< Integer,Integer> hMap=new HashMap<Integer, Integer>();
	for (int idx=0; idx < arr.length; idx++) {
		if (hMap.containsKey(arr[idx])){
			int freq=hMap.get(arr[idx]);
			hMap.put(arr[idx], ++freq);
		}else {
			hMap.put(arr[idx], 1);
		}			
	}
	int[] retVal=new int[2];
	for (int idx=1; idx <= n; idx++) {
		if (hMap.getOrDefault(idx,0)==0) {
			retVal[0]=idx;
		}
		if (hMap.getOrDefault(idx,0)==2) {
			retVal[1]=idx;
		}
	}
	return retVal;		
}
	
	
 public static void main(String[] args) {
	
	HashMapSetMismatch hp=new HashMapSetMismatch();
	int[] retVal;
	try {
	int[] intArray1 = {1,2,4,4,5};
	int n=5;
	printArraySummary(intArray1, "Original Array:");
	System.out.print("n= "+n);
	retVal=hp.hashMapSetMismatch(intArray1, n);
	System.out.print("\nMissing number: "+retVal[0]+ " Duplicate number: "+retVal[1]);
			
	int[] intArray2 = {1,2,3,4,5,5};
	n=6;
	printArraySummary(intArray2, "Original Array:");
	System.out.print("n= "+n);
	retVal=hp.hashMapSetMismatch(intArray2, n);
	System.out.print("\nMissing number: "+retVal[0]+ " Duplicate number: "+retVal[1]);
			
	int[] intArray3 = {1,1,2,3,4,5,6};
	n=7;
	printArraySummary(intArray3, "Original Array:");
	System.out.print("n= "+n);
	retVal=hp.hashMapSetMismatch(intArray3, n);
	System.out.print("\nMissing number: "+retVal[0]+ " Duplicate number: "+retVal[1]);
			
	int[] intArray4 = {1,4,3,4};
	n=4;
	printArraySummary(intArray4, "Original Array:");
	System.out.print("n= "+n);
	retVal=hp.hashMapSetMismatch(intArray4, n);
	System.out.print("\nMissing number: "+retVal[0]+ " Duplicate number: "+retVal[1]);
			
			
			
			
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
				
}
 
 public static void printArraySummary(int[] intArray, String label) throws Exception {
	   	// Case 1: The input Array is null !!
		if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
		// Case 2: Print input Array by index (first to last)
		System.out.println();
		System.out.println("************************************************************************");
		System.out.print(label+" : ");
		int arrayIndex=0;
		for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
				System.out.print(intArray[arrayIndex]);
				if (arrayIndex< intArray.length-1) {System.out.print(",");}
		} 
		System.out.println();
		System.out.println("*************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
	}

}