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.

Powered By
CHP Adblock Detector Plugin | Codehelppro