HackerEarth Supreme Subset problem solution

In this HackerEarth Supreme Subset problem solution we have given a multiset of integers having cardinality n, find its Supreme Subset.

A supreme subset of a given multiset is one of its subsets in which –

if any two elements i, j are chosen from the subset, |i – j| is divisible by m, where x represents the absolute value of x.

it has the highest cardinality/size among all candidate subsets satisfying condition 1.

If there are multiple subsets satisfying the above 2 conditions, the supreme subset is the one that is smallest by set comparison.

Finding order by set comparison – Given two sets of the same size, the smaller one is defined to be the one which is lexicographically smaller when both sets are arranged in non-decreasing order, for example, the set {3,2,1} is smaller than {3,2,2}.

HackerEarth Supreme Subset problem solution.

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

#define ff first 
#define ss second

int main(){
    int i,j,n,m,el,maxi,flag,mod;
    vector<int> ans;
    map<int, int> counter;
    int arr[100005];
    scanf("%d %d", &n, &m);
    for(i = 0; i < n; i++){
        scanf("%d", &arr[i]);
        counter[arr[i] % m]++;
    }

    maxi = 0;
    for(auto el : counter)
        maxi = max(maxi, el.ss);

    sort(arr, arr + n);
    flag = 0;
    mod = 0;
    for(i = 0; i < n; i++){
        if(flag == 0 && counter[arr[i] % m] == maxi){
            flag = 1;
            ans.push_back(arr[i]);
            mod = arr[i] % m;
        }
        else if(flag == 1 && arr[i] % m == mod){
            ans.push_back(arr[i]);
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for(auto el : ans)
        printf("%d ", el);
    printf("n");
    
    return 0;
}

Second solution

#include <bits/stdc++.h>
#define ff first
#define ss second
 
using namespace std;


unordered_map< int, vector<int> > arr;

void verify(int n, int l, int r){
    assert(n >= l && n <= r);
}


 
int main(){

    arr.reserve(1024*256);
    arr.max_load_factor(0.25);

    int n, m;
    scanf("%d%d", &n, &m);
    verify(n, 1, 1000*10000);
    verify(m, 1, 100000*10000);

    while(n--){

        int val;
        scanf("%d", &val);
        verify(val, 1, 100000*10000);
        arr[val % m].push_back(val);
    }

    vector<int> ans;
    for(auto it : arr){

        vector<int> &temp = it.ss;
        sort(temp.begin(), temp.end());

        if((int)temp.size() > (int)ans.size()){
            ans = temp;
        }
        else if((int)temp.size() == (int)ans.size() && temp < ans){
            ans = temp;
        }
    }

    printf("%dn", (int)ans.size());
    for(auto it : ans)
        printf("%d ", it);
    return 0;
}

coding problems