Minimum operations to make GCD of array a multiple of k

Understanding the Statement

We are given an array and k, we need to find the minimum operations needed to make GCD of the array equal or multiple of k. Here an operation means either increment or decrement an array element by 1.

Example

Input : a = { 3, 5, 7 }, k = 5
Output: 4
Explanation: We can increase 3 by 1 and we have to do it two times so that it becomes 5 and decrease 7 by 1 so that it becomes 5, it will also require 2 operations. Hence minimum operation will be 4

Explanation of Code

Here the array value can be nearer to k or any of its multiple. We will count the minimum operations require to make the array value equal to k or to any of its multiple.By doing this we will achieve our solution as if every element is multiple of k then it’s GCD will be at least k. Now our next step would be getting the minimum operations required. This can be done by taking the remainder of each number by k. And we will take the minimum of the two , remainder value or (k- remainder) value.
If we take remainder value this means we are decreasing the value.(using decrement operations)
If we take (k-remainder) value this means we are increasing the value (using increment operations)

Pseudocode

Step 1: Initialize a variable result to 0;
Step 2: For each element in the array check if it is not equal to 1 and is greater than k
Step 3: If the condition matches then take out the remainder of the element when divided by k.
Step 4: Compare remainder and the difference between k and remainder.
Step 5: Add the smaller value to the variable result.
Step 6: if the condition does not matches then add the difference of k and element to result variable.
Step 7: Return result.

Implementations

• C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
        int arr[] = { 3, 5, 7 };
        int size = sizeof(arr) / sizeof(arr[0]);
        int k = 5, minimum;
        int result = 0,i=0;
         while(i < size) {    
       			 //if not equal to 1 and greater that k then increment and 
       			 //decrement both can be done
       		 if (arr[i] != 1 && arr[i] > k) {
        		minimum=min(arr[i] % k, k - arr[i] % k);
                result = result + minimum;
            }
       		 else {
           		//only one choice i.e. to increment.
                result = result + k - arr[i];
            }
            i++;
     }
     cout<<result;
        return 0;
}