Maximum distinct elements after removing k elements
Last Updated :
22 Jan, 2023
Given an array arr[] containing n elements. The problem is to find the 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:
- Make a multi set from the given array.
- During making this multiset check if the current element is present or not in multiset, if it is already present then simply reduce the k value and do not insert in the multiset.
- If k becomes 0 then simply just put values in multiset.
- After traversing the whole given array,
- If k is not equal to zero then it means the multiset is consist of only unique elements and we have to remove any of the k elements from the multiset to make k=0, so in this case the answer will be size of multiset minus k value at that time.
- If k is equal to zero then it means there may be duplicate values present in the multiset so put all the values in a set and the size of this set will be the number of distinct elements after removing k elements
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxDistinctNum(int a[], int n, int k)
{
int i;
multiset<int> s;
for(i=0;i<n;i++){
if(s.find(a[i])==s.end()||k==0)
s.insert(a[i]);
else
{
k--;
}
}
if(k!=0)
return s.size()-k;
else{
set<int> st;
for(auto it:s){
st.insert(it);
}
return st.size();
}
}
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
import java.util.*;
class GFG {
static int maxDistinctNum(int arr[], int n, int k)
{
HashMap<Integer, Integer> numToFreq
= new HashMap<>();
for (int i = 0; i < n; i++) {
numToFreq.put(arr[i],
numToFreq.getOrDefault(arr[i], 0)
+ 1);
}
int result = 0;
PriorityQueue<Integer> minHeap
= new PriorityQueue<Integer>();
for (Map.Entry<Integer, Integer> p :
numToFreq.entrySet()) {
if (p.getValue() == 1)
++result;
else
minHeap.add(p.getValue());
}
while (k != 0 && !minHeap.isEmpty()) {
Integer t = minHeap.poll();
if (t == 1) {
++result;
}
else {
--t;
--k;
minHeap.add(t);
}
}
return result;
}
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));
}
}
|
Python3
def maxDistinctNum(a, n, k):
s = {}
for i in range(n):
if a[i] not in s or k == 0:
s[a[i]] = s.get(a[i], 0)+1
else:
s[a[i]] = 1
k -= 1
if k != 0:
return len(s)-k
else:
st = set()
for i in s:
st.add(i)
return len(st)
if __name__ == "__main__":
arr = [5, 7, 5, 5, 1, 2, 2]
K = 3
N = len(arr)
print("Maximum distinct elements = ", maxDistinctNum(arr, N, K))
|
C#
using System;
using System.Linq;
using System.Collections.Generic;
class MainClass {
public static int maxDistinctNum(int[] a, int n, int k) {
HashSet<int> s = new HashSet<int>();
for(int i=0;i<n;i++){
if(!s.Contains(a[i]) || k==0)
s.Add(a[i]);
else
{
k--;
}
}
if(k!=0)
return s.Count()-k;
else{
return s.Distinct().Count();
}
}
public static void Main (string[] args) {
int[] arr = { 5, 7, 5, 5, 1, 2, 2 };
int n = arr.Length;
int k = 3;
Console.WriteLine("Maximum distinct elements = " + maxDistinctNum(arr, n, k));
}
}
|
Javascript
<script>
function maxDistinctNum(a, n, k)
{
var i;
var s = [];
for(i=0;i<n;i++){
if(!s.includes(a[i])||k==0)
s.push(a[i]);
else
{
k--;
}
}
if(k!=0)
return s.size-k;
else{
var st = new Set();
s.forEach(element => {
st.add(element);
});
return st.size;
}
}
var arr = [5, 7, 5, 5, 1, 2, 2];
var n = arr.length;
var k = 3;
document.write( "Maximum distinct elements = "
+ maxDistinctNum(arr, n, k));
</script>
|
Output
Maximum distinct elements = 4
Time Complexity: O(k*logd), where d is the number of distinct elements in the given array.
Auxiliary Space: O(N), because we are using multiset.
Another Approach: Follow the below steps, to solve this problem:
- Find the Number of distinct Toys.
- Sum of number of element except one element form every distinct Toys.
- Check sum if greater than or equal K then Return all distinct element.
- Otherwise decrement number of distinct element and to fill K.
- Return Size of vector.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int MaxNumber(int arr[], int N, int K)
{
unordered_map<int, int> mp;
for (int i = 0; i < N; i++) {
mp[arr[i]]++;
}
vector<int> v1;
for (auto i : mp) {
v1.push_back(i.second);
}
int temp = 0;
for (int i = 0; i < v1.size(); i++) {
temp += v1[i] - 1;
}
if (K <= temp) {
return v1.size();
}
else {
K = K - temp;
int ans = v1.size();
while (K) {
ans--;
K--;
}
return ans;
}
}
int main()
{
int arr[] = { 10, 10, 10, 50, 50 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << MaxNumber(arr, N, K) << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
static int MaxNumber(int[] arr, int N, int K)
{
HashMap<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < N; i++) {
mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
}
List<Integer> v1 = new ArrayList<>();
for (Map.Entry<Integer, Integer> i :
mp.entrySet()) {
v1.add(i.getValue());
}
int temp = 0;
for (int i = 0; i < v1.size(); i++) {
temp += v1.get(i) - 1;
}
if (K <= temp) {
return v1.size();
}
else {
K = K - temp;
int ans = v1.size();
while (K != 0) {
ans--;
K--;
}
return ans;
}
}
public static void main(String[] args)
{
int arr[] = { 10, 10, 10, 50, 50 };
int K = 3;
int N = arr.length;
System.out.println(MaxNumber(arr, N, K));
}
}
|
Python3
def MaxNumber(arr, N, K):
mp = {}
for i in range(N):
if arr[i] not in mp:
mp[arr[i]] = 0
mp[arr[i]] += 1
v1 = []
for i in mp:
v1.append(mp[i])
temp = 0
for i in range(len(v1)):
temp += v1[i]-1
if K <= temp:
return len(v1)
else:
K = K-temp
ans = len(v1)
while K:
ans -= 1
K -= 1
return ans
if __name__ == "__main__":
arr = [10, 10, 10, 50, 50]
K = 3
N = len(arr)
print(MaxNumber(arr, N, K))
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG {
static int MaxNumber(int[] arr, int N, int K)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
for (int i = 0; i < N; i++) {
if (mp.ContainsKey(arr[i])) {
mp[arr[i]]++;
}
else {
mp.Add(arr[i], 1);
}
}
ArrayList v1 = new ArrayList();
foreach(KeyValuePair<int, int> i in mp)
{
v1.Add(i.Value);
}
int temp = 0;
for (int i = 0; i < v1.Count; i++) {
temp += (int)v1[i] - 1;
}
if (K <= temp) {
return v1.Count;
}
else {
K = K - temp;
int ans = v1.Count;
while (K != 0) {
ans--;
K--;
}
return ans;
}
}
static public void Main()
{
int[] arr = { 10, 10, 10, 50, 50 };
int K = 3;
int N = arr.Length;
Console.WriteLine(MaxNumber(arr, N, K));
}
}
|
Javascript
<script>
function MaxNumber(arr, N, K) {
let mp = new Map();
for (let i = 0; i < N; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1);
} else {
mp.set(arr[i], 1);
}
}
let v1 = [];
for (let i of mp) {
v1.push(i[1]);
}
let temp = 0;
for (let i = 0; i < v1.length; i++) {
temp += v1[i] - 1;
}
if (K <= temp) {
return v1.length;
} else {
K = K - temp;
let ans = v1.length;
while (K) {
ans--;
K--;
}
return ans;
}
}
let arr = [10, 10, 10, 50, 50];
let K = 3;
let N = arr.length;
console.log(MaxNumber(arr, N, K));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Please Login to comment...