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