CC-19 : Find Missing numbers.

Description:

Given input array arr, find the smallest and the largest integer. Then find all integers between smallest and largest that are missing in arr and return the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
intArray = {2,8};	Missing numbers : 3,4,5,6,7
intArray = {2,4,8};	Missing numbers : 3,5,6,7
intArray = {11, 14, 19, 23,25,28};	Missing numbers : 12,13,15,16,17,18,20,21,22,24,26,27

Pseudocode:

The java method should accept following input parameters: arr (int array).

Initialize a variable set of type HashSet to hold the input elements.

Initialize a variable min to hold the smallest int from arr. Set min to Integer.MAX_VALUE. This will help us to find the smallest int in arr.

Initialize a variable max to hold the largest int from arr. Set min to Integer.MIN_VALUE. This will help us to find the largest int in arr.

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

If arr[idx] is less than min, then set min to arr[Idx].

If arr[idx] is greater than max, then set max to arr[Idx].

At end of above loop min and max contain the values of the smallest and largest int in arr.

Initialize int array retSubArr to hold the list of missing numbers between min and max in arr. The number of missing characters between min and max that are absent in arr can be found by (max-min-arr.length-1). Set the size of retSubArr to (max-min-arr.length-1).

Using a for loop iterate using idx as a loop variable with initial value min+1 and increment idx till it reaches max-1:

If set does not contain idx, we have found a missing int between min and max that is not already present in arr. Add idx to retSubArr.

After the above loop completes, retSubArr contains all the ints between min and max that are not already present in arr. Return retSubArr.

Code:

public int[] setArraysFindUniqueSubarrays(int[] arr) {
	HashSet<Integer> set=new HashSet<Integer>();
	int min=Integer.MAX_VALUE;
	int max=Integer.MIN_VALUE;
	for (int idx=0; idx < arr.length; idx++) {
		if (arr[idx] < min) {
			min=arr[idx];			
		}
		if (arr[idx] > max) {
			max=arr[idx];			
		}
		set.add(arr[idx]);
	}
	System.out.println(max-min-arr.length+1);
	int retSubArr[]= new int[max-min-arr.length+1];
	int retIdx=0;
	for (int idx=min+1; idx < max; idx++) {
		if (!set.contains(idx)) {
			retSubArr[retIdx]=idx;
			retIdx++;
		}
	}
	return retSubArr;
}

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.HashSet;


public class SetFindMissingNumbers {
	
public int[] setArraysFindUniqueSubarrays(int[] arr) {
	HashSet<Integer> set=new HashSet<Integer>();
	int min=Integer.MAX_VALUE;
	int max=Integer.MIN_VALUE;
	for (int idx=0; idx < arr.length; idx++) {
		if (arr[idx] < min) {
			min=arr[idx];			
		}
		if (arr[idx] > max) {
			max=arr[idx];			
		}
		set.add(arr[idx]);
	}
	System.out.println(max-min-arr.length+1);
	int retSubArr[]= new int[max-min-arr.length+1];
	int retIdx=0;
	for (int idx=min+1; idx < max; idx++) {
		if (!set.contains(idx)) {
			retSubArr[retIdx]=idx;
			retIdx++;
		}
	}
	return retSubArr;
}


	
public static void main(String[] args) {
		
	SetFindMissingNumbers sp=new SetFindMissingNumbers();
	int[] retVal;
	try {
	int[] intArray1 = {2,8};
	printArraySummary(intArray1, "Original Array");
	retVal=sp.setArraysFindUniqueSubarrays(intArray1);
	printArraySummary(retVal, "Missing numbers");
			
	int[] intArray2 = {2,4,8};
	printArraySummary(intArray2, "Original Array");
	retVal=sp.setArraysFindUniqueSubarrays(intArray2);
	printArraySummary(retVal, "Missing numbers");
			
	int[] intArray3 = {11, 28};
	printArraySummary(intArray3, "Original Array");
	retVal=sp.setArraysFindUniqueSubarrays(intArray3);
	printArraySummary(retVal, "Missing numbers");
			
	int[] intArray4 = {11, 14, 19, 23,25,28};
	printArraySummary(intArray4, "Original Array");
	retVal=sp.setArraysFindUniqueSubarrays(intArray4);
	printArraySummary(retVal, "Missing numbers");
			
			
	}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;
}			
		
		

}