PROBLEM LINK:
PRACTICE
Editorialist: Indrajit Kabiraj
DIFFICULTY:
EASY
PREREQUISITES:
Number Theory
PROBLEM:
It’s the time for IPL auction and you have an array of N Players and an integer K i.e the Number of teams. Each player has a base price of A[i] .You are allowed to perform an operation several times.
You can choose any two players let it be I and J (1<=I< j <=n) present in the array which has the same remainder when their base price divided by k and you have to erase data of those two players and append the absolute value of subtraction of their base price( abs(A[i]-A[j]) ) into the array.(Note: The size of the array will decrease by 1 after an operation is performed).
Your task is to find what is the minimum size of the array we can get after performing the operation as many times as you want.
EXPLANATION:
As the problem statement states, we can only perform the operation if we have more than one number having the same remainder when divided by K. When we subtract two numbers that have the same remainder of R(say). The resultant number that is abs(A[i]-A[j]) always has the remainder of 0.
Firstly, We make an array count of size K and for each number A[i] we add 1 to index (A[i]%K). Now for any index other than 0, we check if the count is odd or even. If it is odd then we just add 1 to the answer because each time we take two elements that have the remainder of R and append the absolute value of their subtraction that have the remainder of 0. Now for index zero at least one element will be there(size of the array can’t be zero) hence the result will be answer + 1.
SOLUTION:
#include<bits/stdc++.h>
using namespace std;
signed main(){
int tc=1;
while(tc--){
int n,k;
cin>>n>>k;
vector<int> V(k);
for(int i=0;i<n;i++){
int x;
cin>>x;
V[x%k]+=1;
}
int count=1;
for(int i=1;i<k;i++){
if(V[i]&1)
count++;
}
cout<<count<<endl;
}
}