Find the min number of move to make all the elements divisible by k

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:

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.