Dada una array y k, necesitamos encontrar las operaciones mínimas necesarias para hacer que el GCD de la array sea igual o múltiplo de k. Aquí, una operación significa incrementar o disminuir un elemento de array en 1.
Ejemplos:
Entrada: a = { 4, 5, 6 }, k = 5
Salida: 2
Explicación: Podemos aumentar 4 en 1 para que se convierta en 5 y disminuir 6 en 1 para que se convierta en 5. Por lo tanto, la operación mínima será 2.
Entrada : a = { 4, 9, 6 }, k = 5
Salida : 3
Explicación: Al igual que en el ejemplo anterior, podemos aumentar y disminuir 4 y 6 en 1 y aumentar 9 en 1 para que se convierta en 10. Ahora cada elemento tiene MCD 5. Por lo tanto, la operación mínima será 3.
Aquí tenemos que hacer que el mcd del arreglo sea igual o múltiplo de k, lo que significa que habrá casos en los que algunos elementos estén cerca de k o de alguno de sus múltiplos. Entonces, para resolver esto, solo tenemos que hacer que cada valor de array sea igual o múltiplo de K. Al hacer esto, lograremos nuestra solución como si cada elemento fuera múltiplo de k, entonces su GCD será al menos K. Ahora nuestro próximo objetivo es para convertir los elementos de la array en la operación mínima, es decir, el número mínimo de incrementos y decrementos. Este valor mínimo de incremento o decremento sólo puede conocerse tomando el resto de cada número de K, es decir, tenemos que tomar el valor del resto o el valor (k-resto), el que sea mínimo entre ellos.
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to make GCD of array a multiple
// of k.
#include <bits/stdc++.h>
using namespace std;
int MinOperation(int a[], int n, int k)
{
int result = 0;
for (int i = 0; i < n; ++i) {
// If array value is not 1 and it is greater than k
// then we can increase the or decrease the
// remainder obtained by dividing k from the ith
// value of array so that we get the number which is
// either closer to k or its multiple
if (a[i] != 1 && a[i] > k)
result = result + min(a[i] % k, k - a[i] % k);
else
// Else we only have one choice which is to
// increment the value to make equal to k
result = result + k - a[i];
}
return result;
}
// Driver code
int main()
{
int arr[] = { 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout << MinOperation(arr, n, k);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to make GCD of array a multiple of k.
#include <stdio.h>
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int MinOperation(int a[], int n, int k)
{
int result = 0;
for (int i = 0; i < n; ++i) {
// If array value is not 1 and it is greater than k
// then we can increase the or decrease the
// remainder obtained by dividing k from the ith
// value of array so that we get the number which is
// either closer to k or its multiple
if (a[i] != 1 && a[i] > k)
result = result + min(a[i] % k, k - a[i] % k);
else
// Else we only have one choice which is to
// increment the value to make equal to k
result = result + k - a[i];
}
return result;
}
// Driver code
int main()
{
int arr[] = { 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
printf("%d", MinOperation(arr, n, k));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to make GCD of array a multiple of k.
import java.io.*;
class GFG {
static int MinOperation(int a[], int n, int k)
{
int result = 0;
for (int i = 0; i < n; ++i) {
// If array value is not 1 and it is greater
// than k then we can increase the or decrease
// the remainder obtained by dividing k from the
// ith value of array so that we get the number
// which is either closer to k or its multiple
if (a[i] != 1 && a[i] > k)
result = result + Math.min(a[i] % k, k - a[i] % k);
else
// Else we only have one choice which is
// to increment the valueto make equal
// to k
result = result + k - a[i];
}
return result;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 5, 6 };
int n = arr.length;
int k = 5;
System.out.println(MinOperation(arr, n, k));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python 3 program to make GCD # of array a multiple of k. def MinOperation(a, n, k): result = 0 for i in range(n) : ''' If array value is not 1 and it is greater than k then we can increase the or decrease the remainder obtained by dividing k from the ith value of array so that we get the number which is either closer to k or its multiple ''' if (a[i] != 1 and a[i] > k) : result = (result + min(a[i] % k, k - a[i] % k)) else : # Else we only have one choice # which is to increment the value # to make equal to k result = result + k - a[i] return result # Driver code if __name__ == "__main__": arr = [ 4, 5, 6 ] n = len(arr) k = 5 print(MinOperation(arr, n, k)) # This code is contributed # by ChitraNayal
C#
// C# program to make GCD
// of array a multiple of k.
using System;
public class GFG{
static int MinOperation(int []a,
int n, int k)
{
int result = 0;
for (int i = 0; i < n; ++i)
{
// If array value is not 1
// and it is greater than k
// then we can increase the
// or decrease the remainder
// obtained by dividing k
// from the ith value of array
// so that we get the number
// which is either closer to k
// or its multiple
if (a[i] != 1 && a[i] > k)
{
result = result +
Math.Min(a[i] % k,
k - a[i] % k);
}
else
{
// Else we only have one
// choice which is to
// increment the value
// to make equal to k
result = result + k - a[i];
}
}
return result;
}
// Driver code
static public void Main (){
int []arr = {4, 5, 6};
int n = arr.Length;
int k = 5;
Console.WriteLine(MinOperation(arr, n, k));
}
}
// This code is contributed
// by Tushil
PHP
<?php
// PHP program to make
// GCD of array a multiple
// of k.
function MinOperation($a, $n, $k)
{
$result = 0;
for ($i = 0; $i < $n; ++$i)
{
// If array value is
// not 1 and it is
// greater than k then
// we can increase the
// or decrease the remainder
// obtained by dividing
// k from the ith value of
// array so that we get the
// number which is either
// closer to k or its multiple
if ($a[$i] != 1 && $a[$i] > $k)
{
$result = $result + min($a[$i] %
$k, $k -
$a[$i] % $k);
}
else
{
// Else we only have one
// choice which is to
// increment the value
// to make equal to k
$result = $result +
$k - $a[$i];
}
}
return $result;
}
// Driver code
$arr = array(4, 5, 6);
$n = sizeof($arr) /
sizeof($arr[0]);
$k = 5;
echo MinOperation($arr, $n, $k);
// This code is contributed
// by @ajit
?>
Javascript
<script>
// Javascript program to make
// GCD of array a multiple
// of k.
function MinOperation(a, n, k)
{
let result = 0;
for (let i = 0; i < n; ++i)
{
// If array value is
// not 1 and it is
// greater than k then
// we can increase the
// or decrease the remainder
// obtained by dividing
// k from the ith value of
// array so that we get the
// number which is either
// closer to k or its multiple
if (a[i] != 1 && a[i] > k)
{
result = result + Math.min(a[i] %
k, k -
a[i] % k);
}
else
{
// Else we only have one
// choice which is to
// increment the value
// to make equal to k
result = result +
k - a[i];
}
}
return result;
}
// Driver code
let arr = [4, 5, 6];
let n = arr.length;
let k = 5;
document.write(MinOperation(arr, n, k));
// This code is contributed
// by _saurabh_jaiswal
</script>
2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA