Dados dos enteros X e Y , la tarea es hacer que X e Y sean iguales dividiendo X o Y por 2 , 3 o 5 , un número mínimo de veces, si se encuentra que es divisible. Si los dos enteros se pueden hacer iguales, imprima «-1» .
Ejemplos:
Entrada: X = 15, Y = 20
Salida: 3
Explicación:
Operación 1: Reducir X(= 15) a 15/3, es decir, X = 15/3 = 5.
Operación 2: Reducir Y(= 20) a 20/2 es decir, Y = 20/2 = 10.
Operación 3: Reducir Y(= 20) a 10/2, es decir, Y = 10/2 = 5.
Después de las operaciones anteriores, X e Y son iguales, es decir, 5.
Por lo tanto, el el número de operaciones requeridas es 3.Entrada: X = 6, Y = 6
Salida: 0
Enfoque: El problema dado se puede resolver con avidez . La idea es reducir los enteros dados a su MCD para hacerlos iguales. Siga los pasos a continuación para resolver el problema:
- Encuentre el Máximo Común Divisor ( MCD ) de X e Y y divida X e Y por su MCD .
- Inicialice una variable, digamos count , para almacenar el número de divisiones requeridas.
- Iterar hasta que X no sea igual a Y y realizar los siguientes pasos:
- Si el valor de X es mayor que Y , entonces intercambie X e Y .
- Si el número más grande (es decir, Y ) es divisible por 2 , 3 o 5 , entonces divídalo por ese número. Incrementa el conteo en 1 . De lo contrario, si no es posible hacer que ambos números sean iguales, imprima «-1» y salga del bucle .
- Después de completar los pasos anteriores, si ambos números se pueden hacer iguales, imprima el valor de conteo como el número mínimo de divisiones requeridas para hacer que X e Y sean iguales.
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 calculate
// GCD of two numbers
int gcd(int a, int b)
{
// Base Case
if (b == 0) {
return a;
}
// Calculate GCD recursively
return gcd(b, a % b);
}
// Function to count the minimum
// number of divisions required
// to make X and Y equal
void minimumOperations(int X, int Y)
{
// Calculate GCD of X and Y
int GCD = gcd(X, Y);
// Divide X and Y by their GCD
X = X / GCD;
Y = Y / GCD;
// Stores the number of divisions
int count = 0;
// Iterate until X != Y
while (X != Y) {
// Maintain the order X <= Y
if (Y > X) {
swap(X, Y);
}
// If X is divisible by 2,
// then divide X by 2
if (X % 2 == 0) {
X = X / 2;
}
// If X is divisible by 3,
// then divide X by 3
else if (X % 3 == 0) {
X = X / 3;
}
// If X is divisible by 5,
// then divide X by 5
else if (X % 5 == 0) {
X = X / 5;
}
// If X is not divisible by
// 2, 3, or 5, then print -1
else {
cout << "-1";
return;
}
// Increment count by 1
count++;
}
// Print the value of count as the
// minimum number of operations
cout << count;
}
// Driver Code
int main()
{
int X = 15, Y = 20;
minimumOperations(X, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate
// GCD of two numbers
static int gcd(int a, int b)
{
// Base Case
if (b == 0)
{
return a;
}
// Calculate GCD recursively
return gcd(b, a % b);
}
// Function to count the minimum
// number of divisions required
// to make X and Y equal
static void minimumOperations(int X, int Y)
{
// Calculate GCD of X and Y
int GCD = gcd(X, Y);
// Divide X and Y by their GCD
X = X / GCD;
Y = Y / GCD;
// Stores the number of divisions
int count = 0;
// Iterate until X != Y
while (X != Y)
{
// Maintain the order X <= Y
if (Y > X)
{
int t = X;
X = Y;
Y = t;
}
// If X is divisible by 2,
// then divide X by 2
if (X % 2 == 0)
{
X = X / 2;
}
// If X is divisible by 3,
// then divide X by 3
else if (X % 3 == 0)
{
X = X / 3;
}
// If X is divisible by 5,
// then divide X by 5
else if (X % 5 == 0)
{
X = X / 5;
}
// If X is not divisible by
// 2, 3, or 5, then print -1
else
{
System.out.print("-1");
return;
}
// Increment count by 1
count += 1;
}
// Print the value of count as the
// minimum number of operations
System.out.println(count);
}
// Driver Code
static public void main(String args[])
{
int X = 15, Y = 20;
minimumOperations(X, Y);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach
# Function to calculate
# GCD of two numbers
def gcd(a, b):
# Base Case
if (b == 0):
return a
# Calculate GCD recursively
return gcd(b, a % b)
# Function to count the minimum
# number of divisions required
# to make X and Y equal
def minimumOperations(X, Y):
# Calculate GCD of X and Y
GCD = gcd(X, Y)
# Divide X and Y by their GCD
X = X // GCD
Y = Y // GCD
# Stores the number of divisions
count = 0
# Iterate until X != Y
while (X != Y):
# Maintain the order X <= Y
if (Y > X):
X, Y = Y, X
# If X is divisible by 2,
# then divide X by 2
if (X % 2 == 0):
X = X // 2
# If X is divisible by 3,
# then divide X by 3
elif (X % 3 == 0):
X = X // 3
# If X is divisible by 5,
# then divide X by 5
elif (X % 5 == 0):
X = X // 5
# If X is not divisible by
# 2, 3, or 5, then print -1
else:
print("-1")
return
# Increment count by 1
count += 1
# Print the value of count as the
# minimum number of operations
print (count)
# Driver Code
if __name__ == '__main__':
X, Y = 15, 20
minimumOperations(X, Y)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to calculate
// GCD of two numbers
static int gcd(int a, int b)
{
// Base Case
if (b == 0) {
return a;
}
// Calculate GCD recursively
return gcd(b, a % b);
}
// Function to count the minimum
// number of divisions required
// to make X and Y equal
static void minimumOperations(int X, int Y)
{
// Calculate GCD of X and Y
int GCD = gcd(X, Y);
// Divide X and Y by their GCD
X = X / GCD;
Y = Y / GCD;
// Stores the number of divisions
int count = 0;
// Iterate until X != Y
while (X != Y) {
// Maintain the order X <= Y
if (Y > X) {
int t = X;
X = Y;
Y = t;
}
// If X is divisible by 2,
// then divide X by 2
if (X % 2 == 0) {
X = X / 2;
}
// If X is divisible by 3,
// then divide X by 3
else if (X % 3 == 0) {
X = X / 3;
}
// If X is divisible by 5,
// then divide X by 5
else if (X % 5 == 0) {
X = X / 5;
}
// If X is not divisible by
// 2, 3, or 5, then print -1
else {
Console.WriteLine("-1");
return;
}
// Increment count by 1
count++;
}
// Print the value of count as the
// minimum number of operations
Console.WriteLine(count);
}
// Driver Code
static public void Main()
{
int X = 15, Y = 20;
minimumOperations(X, Y);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to calculate
// GCD of two numbers
function gcd(a , b) {
// Base Case
if (b == 0) {
return a;
}
// Calculate GCD recursively
return gcd(b, a % b);
}
// Function to count the minimum
// number of divisions required
// to make X and Y equal
function minimumOperations(X , Y) {
// Calculate GCD of X and Y
var GCD = gcd(X, Y);
// Divide X and Y by their GCD
X = X / GCD;
Y = Y / GCD;
// Stores the number of divisions
var count = 0;
// Iterate until X != Y
while (X != Y) {
// Maintain the order X <= Y
if (Y > X) {
var t = X;
X = Y;
Y = t;
}
// If X is divisible by 2,
// then divide X by 2
if (X % 2 == 0) {
X = X / 2;
}
// If X is divisible by 3,
// then divide X by 3
else if (X % 3 == 0) {
X = X / 3;
}
// If X is divisible by 5,
// then divide X by 5
else if (X % 5 == 0) {
X = X / 5;
}
// If X is not divisible by
// 2, 3, or 5, then print -1
else {
document.write("-1");
return;
}
// Increment count by 1
count += 1;
}
// Print the value of count as the
// minimum number of operations
document.write(count);
}
// Driver Code
var X = 15, Y = 20;
minimumOperations(X, Y);
// This code contributed by Rajput-Ji
</script>
Producción:
3
Complejidad de tiempo: O(log(max(X, Y)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kothawade29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA