Non-Divisible Subset

QUESTION

Given a set, S, of n distinct integers, print the size of a maximal subset, S’, of S where the sum of any 2 numbers in S’ is not evenly divisible by k.\n\nInput Format\n\nThe first line contains 2 space-separated integers, n and k, respectively. \nThe second line contains n space-separated integers (we’ll refer to the ith value as ai) describing the unique values of the set.\n\nConstraints\n1<=n<=10^5 1<=k<=100 1<=ai<=10^9\nAll of the given numbers are distinct.\nOutput Format\n\nPrint the size of the largest possible subset (S’).

ANSWER

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() { 
int n,k,i,c=0;
cin>>n>>k;
int arr[n];
for(i=0;i<n;i++) {
cin>>arr[i];
}
int b[k];
for(i=0;i<k;i++) {
b[i]=0;
}
for(i=0;i<n;i++) {
b[arr[i]%k]+=1;
}
c=min(b[0],1);
for(i=1;i<k/2+1;i++) {
if(i!=k-i) {
c+=max(b[i],b[k-i]);
}
}
if(k%2==0) c++;
cout<<c;
return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.