Minimum operations to make GCD of array a multiple of k

December 30, 2021

Minimum operations to make GCD of array a multiple of k

In Minimum operations to make GCD of array a multiple of k problem, we have to perform minimum increment or decrement operations such that the gcd of the array is a multiple of k. In, this article we will provide an explanation with a C++ code.

Minimum operations to make GCD of array a multiple of k

Problem Description

Given an array of n integers and an integer k. You can perform increment and decrement operations on the array element any number of times. Find the minimum operations required to make the gcd of the array a multiple of k.

Solution Explanation

GCD is the greatest common divisor ie a number that divides every element of the array and leaves zero remainder. In this question we need to make GCD of the array multiple of k. So we will increment or decrement every element of the array to nearest multiple of k (greater or smaller).

Time Complexity – O(n)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int minimumOperations(int arr[], int n, int k)
{
    int operations = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= k)
            operations += min(arr[i] % k, k – arr[i] % k);
        else
            operations += (k – arr[i] % k);
    }

    return operations;
}
int main()
{
    int n, k;
    cin >> n >> k;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << minimumOperations(arr, n, k) << endl;
    return 0;
}

Output

5 5
1 2 3 4 5
10

Explanation
1 -> 5 - 4 Operations
2 -> 5 - 3 Operations
3 -> 5 - 2 Operations
4 -> 5 - 1 Operations
5 -> 5 - 0 Operations