PROBLEM LINK:
Author: Vinish
Tester: Vinod
Editorialist: Vinish
DIFFICULTY:
EASY
PREREQUISITES:
SORTING
PROBLEM:
Given an array of n elements sort the array according to its modulo value with given number K
and find the sum of the last M numbers.
EXPLANATION:
Merge sort can be used to sort the array based on modulo values.But we will be looking at a simple solution using the pre-defined sort function which is present in the STL Library of C++.
For sorting an array of n elements we write sort(a,a+n);
We can even write our own compare function which will sort the elements according to the compare function.The compare function for sorting based on modulo looks something like this:
bool comp(int a,int b)
{
if(a%k==b%k)return a<b;
else return a%k<b%k;
}
When we don’t write any compare function the default a<b is taken as the compare function.
After this we have to iterate through the array from the last and find the sum of last M elements.
Use long long int to avoid integer overflow.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Tester’s solution can be found here.