Join Regular Classroom : Visit ClassroomTech

Minimum Distinct Element after Deletion – Infytq 2019 Solve

/ Miscellaneous / By

Problem: Given a list (combination of repeated and distinct elements) and number of elements deletion X. You have to delete any X elements from the list so that list will have minimum distinct number and return the length of the minimum distinct list.

Input Format: The first line contains an integer T. T is the number of independent testcases. For each testcase the first line contains an integer denoting the number of elements you can delete. Next line contains the list. (Inputs are separated by space here.)

Sample Input:

2
2
1 1 2 4
3
1 1 1 2 2 2 4 5 6

Sample Output: 

1
2

Explanation: Here, 2 and 4 are removed so that it has the minimum distinct element 1 which is repeated (repetition are removed) so the length of the minimum distinct list is 1

For the second case, 4, 5 and 6 are removed so that it has the minimum distinct element 1 and 2 which is repeated (repetition are removed) so the length of the minimum distinct list is 2.

Solution: We strongly recommend you to try the problem first before moving to the solution.

Python

# Code to understand the Minimum distinct element problem in Python
# www.codewindow.in

def solve():
    rem=int(input())
    list_num=list(map(int, input().split(" ")))
    list_element_count=[]
    set_distinct=set(list_num)
    for i in set_distinct:
        count=list_num.count(i)
        list_element_count.append(count)
        
    list_element_count.sort()
    
    length=len(list_element_count)
    
    for count in list_element_count:
        if count<=rem:
            rem -= count
            length -= 1
        else:
            break
    print(length)
    
# Driver code
t=int(input())
while(t):
    solve()
    t-=1

C++ (STL)

/* CPP solution */
/* www.codewindow.in */

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int x, c=0;
    string s;
    vector<int> v;

    cin >> x;
    cin.ignore(numeric_limits<streamsize>::max(),'\n'); // ignore the "\n"
    getline(cin, s);
    
    for(int i=0; i<s.length(); i+=2) {  
        int temp=(int)s[i]-48;
        v.push_back(temp);  // push the elemnts as int in a vector
    }
    
    sort(v.begin(), v.end());  // Sort the vector
    
    for(int i=0; i<v.size() && x>0; i+=c) {
        c=count(v.begin(), v.end(), v[i]);  // count frequency
        if(c==1) {
            v.erase(v.begin()+i);   // If unique then remove it until x=0
            --x;
            c=0;
        }
    }
    
    auto it=unique(v.begin(), v.end());  // Iterator for unique elements
    v.resize(distance(v.begin(), it));  // Resize the vector by removing duplicates
    
    cout << v.size() << "\n";   // Print the sizeof vector
}

// Driver code
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t=1;    // Testcases
	cin >> t;
	while(t--)  
	    solve();
	    
	return 0;
}

Input:

2
2
1 1 2 4
3
1 1 1 2 2 2 4 5 6

Output:

1
2

Follow Us

You Missed