Dados dos enteros positivos A y B , la tarea es encontrar el número mínimo de incrementos/decrementos necesarios para realizar en A o B para que ambos números no sean coprimos .
Ejemplos:
Entrada: A = 12, B = 3
Salida: 0
Explicación:
Dado que 12 y 3 ya no son coprimos, el recuento mínimo de operaciones de incremento/decremento requerido es 0.Entrada: A = 7, B = 17
Salida: 2
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si A y B tienen el Máximo Común Divisor mayor que 1 , entonces no se debe realizar ningún incremento o decremento, ya que los números ya no son coprimos.
- Ahora, verifique la diferencia de 1 en ambas direcciones tanto para A como para B. Por lo tanto, solo se requiere un paso para convertir cualquier número en un número par.
- Si no se aplica ninguno de los dos casos anteriores , se requieren 2 operaciones de incrementos/decrementos para hacer que los números A y B sean su número par más cercano para que los números se conviertan en no coprimos .
Con base en las observaciones anteriores, siga los pasos a continuación para resolver el problema:
- Si el GCD de A y B no es igual a 1 , imprima 0 ya que no se requiere ninguna operación.
- De lo contrario, si el MCD de uno de los pares { {A + 1, B} , {A – 1, B} , {A, B + 1} , {A, B – 1} } no es igual a 1 , entonces imprime 1 ya que solo se requiere una operación.
- De lo contrario, imprima 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of // increments/decrements operations required // to make both the numbers non-coprime int makeCoprime(int a, int b) { // If a & b are already non-coprimes if (__gcd(a, b) != 1) return 0; // If a & b can become non-coprimes // by only incrementing/decrementing // a number only once if (__gcd(a - 1, b) != 1 or __gcd(a + 1, b) != 1 or __gcd(b - 1, a) != 1 or __gcd(b + 1, a) != 1) return 1; // Otherwise return 2; } // Driver Code int main() { int A = 7, B = 17; cout << makeCoprime(A, B); return 0; }
Java
// Java program for the above approach public class GFG { // function to calculate gcd static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to find the minimum number of // increments/decrements operations required // to make both the numbers non-coprime static int makeCoprime(int a, int b) { // If a & b are already non-coprimes if (__gcd(a, b) != 1) return 0; // If a & b can become non-coprimes // by only incrementing/decrementing // a number only once if (__gcd(a - 1, b) != 1 || __gcd(a + 1, b) != 1 || __gcd(b - 1, a) != 1 || __gcd(b + 1, a) != 1) return 1; // Otherwise return 2; } // Driver code public static void main(String args[]) { int A = 7, B = 17; System.out.println(makeCoprime(A, B)); } } // This code is contributed by SoumikMondal
Python3
# Python3 program for the above approach from math import gcd # Function to find the minimum number of # increments/decrements operations required # to make both the numbers non-coprime def makeCoprime(a, b): # If a & b are already non-coprimes if (gcd(a, b) != 1): return 0 # If a & b can become non-coprimes # by only incrementing/decrementing # a number only once if (gcd(a - 1, b) != 1 or gcd(a + 1, b) != 1 or gcd(b - 1, a) != 1 or gcd(b + 1, a) != 1): return 1 # Otherwise return 2 # Driver Code if __name__ == '__main__': A = 7 B = 17 print(makeCoprime(A, B)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; class GFG{ // Function to calculate gcd static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // Base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to find the minimum number of // increments/decrements operations required // to make both the numbers non-coprime static int makeCoprime(int a, int b) { // If a & b are already non-coprimes if (__gcd(a, b) != 1) return 0; // If a & b can become non-coprimes // by only incrementing/decrementing // a number only once if (__gcd(a - 1, b) != 1 || __gcd(a + 1, b) != 1 || __gcd(b - 1, a) != 1 || __gcd(b + 1, a) != 1) return 1; // Otherwise return 2; } // Driver Code public static void Main(String[] args) { int A = 7, B = 17; Console.Write(makeCoprime(A, B)); } } // This code is contributed by sanjoy_62
Javascript
<script> // JavaScript program for the above approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find the minimum number of // increments/decrements operations required // to make both the numbers non-coprime function makeCoprime(a, b) { // If a & b are already non-coprimes if (__gcd(a, b) != 1) return 0; // If a & b can become non-coprimes // by only incrementing/decrementing // a number only once if (__gcd(a - 1, b) != 1 || __gcd(a + 1, b) != 1 || __gcd(b - 1, a) != 1 || __gcd(b + 1, a) != 1) return 1; // Otherwise return 2; } // Driver Code let A = 7, B = 17; document.write(makeCoprime(A, B)); // This code is contributed by Potta Lokesh </script>
2
Complejidad de tiempo: O(log(A, B))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA