Java program to find maximum distinct elements after removing k elements

In this module, we are going to discuss the maximum distinct elements from arr[] that are present after removing k elements from the given array. The input constraints areĀ  follows

Input 1: Array arr={32,9,55,9,22,35,9,35}, k=3
Output 1: 5

Input 2: Array arr=={35,36,32,55,50,9},k=4
Output 2: 2

Explanation:

Here, what we have done is if there are any elements that are repeating we will remove the repeating elements first like removing two 9’s in input 1 & one 35 in input 1 which is equal to removing of 3 elements. For, suppose if there are no repeating elements you can remove distinct elements based on the number of removing k elements.

Java Program For Finding Maximum Distinct Elements

import java.io.*;
import java.util.*;
public class distinct
{
	public static Map<Integer,Integer> freq(int ar[],int n1)
	{
		Map<Integer, Integer> map = new HashMap<>(); // creating a HashMap
        for (int i = 0; i < n1; i++) 
        { 
            if (map.containsKey(ar[i]))  // if map contains key increment count of frequency
            { 
                map.put(ar[i], map.get(ar[i]) + 1); 
            }  
            else
            { 
                map.put(ar[i], 1); 
            } 
        } 
        return map;
	}
	public static int result(List<Integer> list1,int k)
	{
	     while (k > 0) { 
                   int rem = list1.remove(0);
                   rem-=1;  
                   if (rem > 0) 
                    {   list1.add(rem); }
                    Collections.sort(list1,Collections.reverseOrder());
                   k-=1; 
             }  
        return list1.size();
	}
    public static void main(String[] args)throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int arr[]=new int[n];
        List<Integer> list=new ArrayList<>();
        String in[]=br.readLine().trim().split("\\s+");
        int k=Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        	arr[i]=Integer.parseInt(in[i]);
        Map<Integer,Integer> mp=new HashMap<>();
        mp=freq(arr,n);
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) //Iterator forHashMap 
        { 
            list.add(entry.getValue());   //add frequencies to list
        } 
        Collections.sort(list,Collections.reverseOrder());
         System.out.println(result(list,k));
    }
}

Input:

8
32 9 55 9 22 35 9 35
3

Output:

5

Input:

6
35 36 32 55 50 9
4

Output:

2

Explanation:

Here first we read the input from the user which is an array, length of array n, and the number of k elements to be removed. Here, we used HashMap to identify the frequencies of elements which is freq() that returns a HashMap with key, value pair.
Later, after obtaining the HashMap we assigned frequency of elements to list called list and we sorted list in decreasing order and passed it to result().

public static int result(List<Integer> list1,int k)
{
while (k > 0) {
int rem = list1.remove(0);// remove starting element
rem--;
if (rem > 0)
{ 
    list1.add(rem);// add elemnt to last
 
}
Collections.sort(list1,Collections.reverseOrder());//sort elements in decreasing order
k--;
}
return list1.size();// return size of list
}

Here, what we are doing is reducing the most frequency count this way we can eliminate duplicates and hereafter removing the most frequency element and reduce it by one and add it to the end of list if it still contains more frequencies with the help of sort() we can bring it to first. The total remaining elements are distinct elements.

 

Leave a Reply