Given an array arr[] containing n elements. The problem is to find maximum number of distinct elements (non-repeating) after removing k elements from the array.
Note: 1 <= k <= n.
Examples:
Input : arr[] = {5, 7, 5, 5, 1, 2, 2}, k = 3 Output : 4 Remove 2 occurrences of element 5 and 1 occurrence of element 2. Input : arr[] = {1, 2, 3, 4, 5, 6, 7}, k = 5 Output : 2 Input : arr[] = {1, 2, 2, 2}, k = 1 Output : 1
Approach: Following are the steps:
- Create a hash table to store the frequency of each element.
- Insert frequency of each element in a max heap.
- Now, perform the following operation k times. Remove an element from the max heap. Decrement its value by 1. After this if element is not equal to 0, then again push the element in the max heap.
- After the completion of step 3, the number of elements in the max heap is the required answer.
C++
// C++ implementation to find maximum distinct // elements after removing k elements #include <bits/stdc++.h> using namespace std; // function to find maximum distinct elements // after removing k elements int maxDistinctNum( int arr[], int n, int k) { // 'um' implemented as hash table to store // frequency of each element unordered_map< int , int > um; // priority_queue 'pq' implemented as // max heap priority_queue< int > pq; // storing frequency of each element in 'um' for ( int i = 0; i < n; i++) um[arr[i]]++; // inserting frequency of each element in 'pq' for ( auto it = um.begin(); it != um.end(); it++) pq.push(it->second); while (k--) { // get the top element of 'pq' int temp = pq.top(); // remove top element from 'pq' pq.pop(); // decrement the popped element by 1 temp--; // if true, then push the element in 'pq' if (temp != 0) pq.push(temp); } // Count all those elements that appear // once after above operations. int res = 0; while (pq.empty() == false ) { int x = pq.top(); pq.pop(); if (x == 1) res++; } return res; } // Driver program to test above int main() { int arr[] = { 5, 7, 5, 5, 1, 2, 2 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; cout << "Maximum distinct elements = " << maxDistinctNum(arr, n, k); return 0; } |
Java
// Java implementation to find maximum distinct // elements after removing k elements import java.util.*; class GFG { // function to find maximum distinct elements // after removing k elements static int maxDistinctNum( int [] arr, int n, int k) { // hash map to store // frequency of each element HashMap<Integer, Integer> map = new HashMap<>(); // priority_queue 'pq' implemented as // max heap PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // storing frequency of each element in map for ( int i = 0 ; i < n; i++) { if (map.containsKey(arr[i])) { int val = map.get(arr[i]); val++; map.remove(arr[i]); map.put(arr[i], val); } else map.put(arr[i], 1 ); } // inserting frequency of each element in 'pq' for (Map.Entry<Integer, Integer> entry : map.entrySet()) { pq.add(entry.getValue()); } while (k > 0 ) { // get the top element of 'pq' int temp = pq.poll(); // decrement the popped element by 1 temp--; // if true, then push the element in 'pq' if (temp > 0 ) pq.add(temp); k--; } // Count all those elements that appear // once after above operations. int res = 0 ; while (pq.size() != 0 ) { pq.poll(); res++; } return res; } // Driver code public static void main(String args[]) { int [] arr = { 5 , 7 , 5 , 5 , 1 , 2 , 2 }; int n = arr.length; int k = 3 ; System.out.println( "Maximum distinct elements = " + maxDistinctNum(arr, n, k)); } } // This code is contributed by rachana soma |
Output:
Maximum distinct elements = 4
Time Complexity: O(k*logd), where d is the number of distinct elements in the given array.
leave a comment
0 Comments