Given an integer k and array of length N find the min no of move to make all the elements divisible by k. In one move you can go one of the below operation.
1. For any index i we can do a[i] = a[i] + p 2. p = p + 1
The value of p starts from the 0.
Example:
Input: arr[]: {1, 2, 3}, k = 3 Output: 3 Explanation: Here we want to make all the element divisible by 3. We will first the operation 2 so the value of the element p will increase to 1. Then we will do operation 1 on the second element. So the array will become {1, 3, 3} and the value of p will become 2. Now we will do a first operation on the first element. So the array will become {3, 3, 3}. So we make 3 operation to make all the element divisible by k. Input: arr[]: {1, 2, 3}, k = 6 Output: 6 Explanation: We will make a second operation three consecutive time. After that the value of the p will become 3. Now we will do first operation on the third element. So the array will become {1, 2, 6} and the value of p will become 4. We will make again a first operation on the second. And first element respectively. after all the operation the array will become {6, 6, 6}. So the operation needed is 6.
Approach:
- We will use the map to store number of occurences of the element we need to add to make a array divisible by k.
- For one occurence of the element we have to go from 0 to k – 1 but if the no of occureces for the needed element is more than one then we have to go till the k*(noofoccureces -1 ) + needed element + 1.
- We will find max occurence and find the value for that because it the no of operation needed that we have to do.
Below is the implementation of the above approach.
#include<bits/stdc++.h> using namespace std; #define ll long long ll findMinNoOfMoves(vector < int > & a, int k) { // size of the array int n = a.size(); // storing the no of occurences // of the remainder of the array map < ll, int > need; // store the max no of // time the remainder occure ll maxOccurence = 0; for (int i = 0; i < n; ++i) { // checking for the value is devisible // by k or not if (a[i] % k != 0) { // storing the needed element we have to // add in to the element need[k - a[i] % k]++; // intialising with max no of time // needed value maxOccurence = max(maxOccurence, (ll) need[k - a[i] % k]); } } // indicate min no of moves required ll ans = 0; for (auto it: need) { if (it.second == maxOccurence) { // finding the min no of moves we have to // do to make all the element devisible by k ans = it.first + (ll) k * (it.second - 1) + 1; } } // returning the min no of moves return ans; } // driver function int main() { int k = 6; vector < int > a = {1,2,3}; cout << findMinNoOfMoves(a, k) << endl; }
output:
6
Time Complexity: O(N)
Auxiliary Space: O(N)
Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.