| 6 | using namespace std; |
| 7 | |
| 8 | void cp(){ |
| 9 | int tmp=0,n,k; |
| 10 | cin>>n>>k; // size of the array and the number k taken as input |
| 11 | ll a[n]; |
| 12 | for(int i=0;i<n;i++) |
| 13 | cin>>a[i]; // input the array elements |
| 14 | for(int i=0;i<n;i++) |
| 15 | a[i] %=k; // array elements are replaced by their remainder with k |
| 16 | |
| 17 | ll hm[k]; // hashmap of size k is constructed and initialised to 0 |
| 18 | memset(hm,0,sizeof(hm)); |
| 19 | |
| 20 | for(ll i=0;i<n;i++){ |
| 21 | hm[a[i]]++; |
| 22 | } |
| 23 | |
| 24 | if(hm[0]!=0){ // if the 0th element is not zero then it counts in the subset |
| 25 | tmp++; |
| 26 | } |
| 27 | |
| 28 | if(k%2==0){ // for even value of k we have |
| 29 | for(ll i=1;i<(k/2);i++){ // we tend to take one of the two values |
| 30 | tmp+= max(hm[i],hm[k-i]); // the two values being ith element and (k-i)th element |
| 31 | } // as the presence of mere one of them will prevent the entire subset from being divisible |
| 32 | |
| 33 | if(hm[k/2]!=0) // if the middlemost element is non zero then it is separately counted |
| 34 | tmp++; |
| 35 | } |
| 36 | |
| 37 | if(k%2!=0){ |
| 38 | for(ll i=1;i<=(k/2);i++){ // same process being repeated when k is odd |
| 39 | tmp+= max(hm[i],hm[k-i]); |
| 40 | } |
| 41 | } // only difference is the middle most element won't count here. |
| 42 | |
| 43 | cout<<tmp<<endl; // the required size of the subset |
| 44 | return ; |
| 45 | |
| 46 | } |
| 47 | |
| 48 | |
| 49 | int main(){ |