Using Java Hashmap to Find the Biggest Number in an Array which Occurs the Same times as the Number Itself

 

Today we'll touch-base on an Interview Question that involves multiple important Java concepts. You deal with Arrays, For loops, If statements, While Statement, Iterators, Java Collections and Function re-usability. 

So, with one single question, your Interviewer can actually assess your expertise in all these areas! Let's check it out!

Today we'll try to find the Biggest Number in an Array, which is occurring the Same number of times as the number itself. 

So, just being the biggest number is not sufficient! If that was what is asked, you can find the max and/or min number of an array with this article. But this is not the question. In order to qualify for an answer, the number should occur the same number of times as the number itself and be the biggest such number. Quite complicated, we should say!

If you follow our blog, we have already published one article on the usage of HashMaps to find if two strings are Anagrams. We'll reuse the Hashmap concept here to segregate the count of a number occurring in an array, and then we'll analyze the HashMap to find the biggest number occurring the same times as the number itself. 

So, the first step is, load the int array into a HashMap. Here's the code to do that:

/**
 * Load an int[] to a HashMap
 * 
 * @author computengine.com
 * @param input
 * @return
 */
public HashMap<Integer, Integer> loadToHashMap(int[] input) {

	HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

	//loop through the array
	for (int i = 0; i < input.length; i++) {
		//data already present in hashmap
		if (hm.containsKey(input[i])) {
			//increment the count and place it back
			Integer count = hm.get(input[i]);
			hm.replace(input[i], count + 1);
		} else {
			//place in hashmap if not present earlier
			hm.put(input[i], 1);
		}
	}

	return hm;
}

We'll loop through the array and put the data into the HashMap as (key,value) pairs. Now that the HashMap is ready, we now need to check the biggest number which occurs the same number of times as the number itself. How do we do that? Its pretty easy now! We need to see which key and value are equal in the HashMap, and find the biggest among them!

Here's the code which will do that:

/**
 * Find the Highest Number which is occurring the same number of times as the
 * number itself
 * 
 * @author computengine.com
 * @param A
 * @return
 */
public int maxNumberwithEqualCount(int[] A) {

	//Load array to HashMap
	HashMap<Integer, Integer> hm = loadToHashMap(A);

	//Initialize an Iterator for the HashMap
	Iterator<Entry<Integer, Integer>> it = hm.entrySet().iterator();

	//a variable to store the max value
	int max = 0;

	//loop through the HashMap
	while (it.hasNext()) {
		Entry<Integer, Integer> ent = it.next();
		//compare key and value
		if (ent.getKey() == ent.getValue()) {
			//store value is max if its greater than previously stored value
			if (ent.getValue() > max) {
				max = ent.getValue();
			}
		}
	}

	return max;
}

Time to check the output !

int[] a = { 1, 2, 3, 4, 3, 2, 2, 3, 4, 3, 2, 5, 4, 3, 3, 2, 2, 2, 3, 4, 5, 5, 5 };

System.out.println("Max number occuring same time as number itself:"+cod.maxNumberwithEqualCount(a));

Output:

Max number occuring same time as number itself:4

If you observe closely, 5 is actually the biggest number in the array, but it occurs 4 times only, so its not eligible for the answer. The number 4 occurs 4 times, and fits the requirement perfectly, which is calculated by our function as well!

Thanks for Reading the Article. If you have reached this far, we hope that the article was useful to you! Please Like/Share/Follow us on Facebook, Twitter, Tumblr.