CC-15 : Reduce input array to half.

Description:

Given an array of integers, find the minimum number of integers to remove to reduce the array size to half. When an integer is removed, all its duplicates are also removed from array. So to have minimum numbers of distinct integers that are removed, remove the integers with duplicates first.

Test cases and expected outputs:

Input Parameters	Expected outputs
Nums : 3,3,3,4,7,9,3,4,10,15,11,1,1,7	Minimum distinct Numbers to be removed to reduce size to half: 3

Pseudocode:

Array of integers is received as input parameter.

Initialize a HashMap named freq which we will use to count the frequency of occurrence of integersx in the input array.

Iterate though nums from index 0 to index chars.length-1:

Check if hashMap already contains nums[idx]. If already present, extract the frequency of the nums[idx] from hashMap. Increment the frequency by 1 and put nums[idx] and the updated frequency back into to the HashMap.

Initialize a PriorityQueue instance named maxHeap.

Iterate through values of hashMap freq:

Add the current value (frequency) to heap.

Initialize variable removedNumsCnt to 0; this is used to count how many count of integers we have removed from the array(including duplicate nums).

Initialize variable removedNumsUnique to 0; this is used to count how many count of integers we have removed from the array(distinct nums).

Initialize variable named half to nums.length/2.

While (removedNumsCnt < half):

Remove frequency value from top of MaxHeap.

Add above frequency to removedNumsCnt.

Increment removedNumsUnique by 1.

Return removedNumsUnique as now it contains the minimum number of integers to remove to reduce the array size to half.

Code:

public int reduceArrToHalf(int[] nums) {
	HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
	for (int idx=0; idx < nums.length; idx++) {
		int currFreq=freq.getOrDefault(nums[idx],0);
		freq.put(nums[idx], currFreq+1);
	}	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	Iterator<Integer> itr=freq.values().iterator();
	while (itr.hasNext()) {
		maxHeap.add((Integer)itr.next());
	}
	int removedNumsCnt=0;
	int removedNumsUnique=0;
	int half=nums.length/2;
	while(removedNumsCnt < half) {
		int numsBeingRemoved=maxHeap.remove();
		removedNumsCnt+=numsBeingRemoved;
		removedNumsUnique++;
	}
	return removedNumsUnique;
}

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.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;

public class HeapReduceArrToHalf {
	
public int reduceArrToHalf(int[] nums) {
	HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
	for (int idx=0; idx < nums.length; idx++) {
		int currFreq=freq.getOrDefault(nums[idx],0);
		freq.put(nums[idx], currFreq+1);
	}	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	Iterator<Integer> itr=freq.values().iterator();
	while (itr.hasNext()) {
		maxHeap.add((Integer)itr.next());
	}
	int removedNumsCnt=0;
	int removedNumsUnique=0;
	int half=nums.length/2;
	while(removedNumsCnt < half) {
		int numsBeingRemoved=maxHeap.remove();
		removedNumsCnt+=numsBeingRemoved;
		removedNumsUnique++;
	}
	return removedNumsUnique;
}

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;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	HeapReduceArrToHalf hp=new HeapReduceArrToHalf();
	int[] nums= {3,3,3,4,7,9,3,4,10,15,11,1,1,7};
	printArraySummary(nums, "Nums");
	retVal=hp.reduceArrToHalf(nums);
	System.out.print("Numbers to be removed to reduce size to half: "+ retVal);	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}