Missing Numbers

I received a message to solve the Missing Numbers challenge from HackerRank. The approach is to read the first list (A) to a HashMap so we would be able to get a count for each key. The process repeats with the second list (B). At that point we can iterate over list A (smaller) and update (subtract) or delete the matching keys from list B (larger). What is left in B is what is needed.

The final detail is to sort the values. For that they are inserted into an array. The array is sorted. The sorted array is displayed in ascending order.

Following is a screen capture of the console from the Eclipse IDE using the sample input:

10
203 204 205 206 207 208 203 204 205 206
13
203 204 204 205 206 207 205 208 203 206 205 206 204
204 205 206 

Following is the Java 8 code for the solution that passed all five test cases:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;

public class Solution {

	/**
	 * 
	 */
	public static void main(String[] args) {

		HashMap<Integer, Integer> A = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> B = new HashMap<Integer, Integer>();
		
		// **** open scanner ****
		
		Scanner sc = new Scanner(System.in);
	
		// **** read first list ****
		
		int n = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < n; i++) {
			int key = sc.nextInt();
			if (A.containsKey(key)) {
				int value = A.get(key);
				value++;
				A.put(key, value);
			} else {
				A.put(key, 1);
			}
		}
		
		// **** read second list ****
		
		int m = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < m; i++) {
			int key = sc.nextInt();
			if (B.containsKey(key)) {
				int value = B.get(key);
				value++;
				B.put(key, value);
			} else {
				B.put(key, 1);
			}
		}
		
		// **** close scanner ****
		
		sc.close();
		
		// **** remove A from B ****
		
		Iterator it = A.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry pair 	= (Map.Entry<Integer, Integer>)it.next();
			int aKey 		= (int)pair.getKey();
			int aValue 		= (int)pair.getValue();
			
			// **** ****
			
			int bValue = B.get(aKey);
			if (bValue == aValue) {
				B.remove(aKey);
			} else {
				bValue -= aValue;
				B.put(aKey, bValue);
			}
		}
		
		// **** populate array of values ****
		
		int[] arr = new int[B.size()];
		it = B.entrySet().iterator();
		for (int i = 0; it.hasNext(); i++) {
			Map.Entry pair 	= (Map.Entry<Integer, Integer>)it.next();
			arr[i] 			= (int)pair.getKey();
		}
		
		// **** sort and display the array ****
		
		Arrays.sort(arr);
		for (int a : arr) {
			System.out.print(a + " ");
		}
		System.out.println();
	}

}

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

Regards;

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *