Given a multi-set of n integers. We have to select exactly k of them in a such way that the difference between any two of them is divisible by m, if it is not possible we will simply return “no” and if it is we will print yes.
Examples:
Input : 3 2 3 //n,k,m respectively 1 8 4 //given multi-set Output :yes Input :3 3 3 //n,k,m respectively 1 8 4 //given multi-set Output :no
Since, we need to find a set of length K such that all pairs have a difference divisible by M, we will start by taking Mod of every element by M.
Now, all elements that are equal will form a set with pairs having a diff. divisible by M.
For example, if M = 3 and Arr[] = { 1, 4, 7, 1, 3}
After applying modulus : Arr[] = { 1, 1, 1, 1, 0}
We can observe that a set is formed by first four elements.
Now, to check if a set of length K is formed or not, we can maintain a count array of length of length M.
If there is an index in the count array for which the value is greater than or equal to K, we found a valid set.
Implementation:
#include <bits/stdc++.h >
using namespace std;
//Function to print K number of pairs
string check(int a[], int n, int m, int k)
{
int c[m + 1] = { 0 };
//count array to check if K pairs can be made or not
for (int i = 0; i < n; i++)
{
c[a[i] % m]++;
}
bool flag = false;
int temp = 0;
for (int i = 0; i <= m; i++) // to check if there K pairs can be made or not
{
if (c[i] >= k)
{
temp = i;
flag = true;
break;
}
}
if (flag)
{
return "Yes";
}
else return "No";
}
//Driver Code
int main()
{
int n = 5; //size of the array
int m = 3; //number from which the differnce must be divisible
int k = 4; //number of pairs which have to be formed
int a[n] = {1,4,7,1,3};
cout << check(a, n, m, k);
}
Output:
Yes
Time complexity of the given code is O(n+m) where n is the size of the array and m is the modulus value.
Space complexity of the code is O(m) as we are using an array of size m+1 to store the count of remainders.