Dado un número N y dos enteros A y B , la tarea es verificar si es posible convertir el número a 1 mediante las siguientes dos operaciones:
- Multiplícalo por A
- dividirlo por B
Si es posible reducir N a 1 , imprima el número mínimo de operaciones requeridas para lograrlo; de lo contrario, imprima «-1» .
Ejemplos:
Entrada: N = 48, A = 3, B = 12
Salida: 3
Explicación:
A continuación se muestran las 3 operaciones:
1. Divide 48 entre 12 para obtener 4.
2. Multiplica 4 por 3 para obtener 12.
3. Divide 12 entre 12 para obtener 1.
Por lo tanto, el número total de operaciones es 3.Entrada: N = 26, A = 3, B = 9
Salida: -1
Explicación:
No es posible convertir 26 a 1.
Enfoque: el problema se puede resolver utilizando el enfoque codicioso . La idea es verificar si B es divisible por A o no y en base a eso tenemos las siguientes observaciones:
- Si B%A != 0 , entonces solo es posible convertir N en 1 si N es completamente divisible por B y se requieren N/B pasos para hacerlo. mientras que si N = 1 , entonces requeriría 0 pasos, de lo contrario es imposible e imprime «-1» .
- Si B%A == 0 , entonces considere una variable C cuyo valor es B/A . Divida N por B , usando la segunda operación hasta que no se pueda dividir más, llamemos al número de división como x.
- Nuevamente divida el N restante por C hasta que no se pueda dividir más, llamemos al número de divisiones en esta operación ser y.
- Si N no es igual a 1 después de las operaciones anteriores, entonces es imposible convertir N en 1 usando las operaciones mencionadas anteriormente y la respuesta será «-1» , pero si es igual a 1, entonces podemos usar la fórmula total_steps = x + (2 * y) para calcular los pasos mínimos totales requeridos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to check if it is possible
// to convert a number N to 1 by a minimum
// use of the two operations
int findIfPossible(int n, int a, int b)
{
// For the Case b % a != 0
if (b % a != 0) {
// Check if n equal to 1
if (n == 1)
return 0;
// Check if n is not
// divisible by b
else if (n % b != 0)
return -1;
else
return (int)n / b;
}
// For the Case b % a == 0
// Initialize a variable 'c'
int c = b / a;
int x = 0, y = 0;
// Loop until n is divisible by b
while (n % b == 0) {
n = n / b;
// Count number of divisions
x++;
}
// Loop until n is divisible by c
while (n % c == 0) {
n = n / c;
// Count number of operations
y++;
}
// Check if n is reduced to 1
if (n == 1) {
// Count steps
int total_steps = x + (2 * y);
// Return the total number of steps
return total_steps;
}
else
return -1;
}
// Driver Code
int main()
{
// Given n, a and b
int n = 48;
int a = 3, b = 12;
// Function Call
cout << findIfPossible(n, a, b);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if it is possible
// to convert a number N to 1 by a minimum
// use of the two operations
static int findIfPossible(int n, int a, int b)
{
// For the Case b % a != 0
if (b % a != 0)
{
// Check if n equal to 1
if (n == 1)
return 0;
// Check if n is not
// divisible by b
else if (n % b != 0)
return -1;
else
return (int)n / b;
}
// For the Case b % a == 0
// Initialize a variable 'c'
int c = b / a;
int x = 0, y = 0;
// Loop until n is divisible by b
while (n % b == 0)
{
n = n / b;
// Count number of divisions
x++;
}
// Loop until n is divisible by c
while (n % c == 0)
{
n = n / c;
// Count number of operations
y++;
}
// Check if n is reduced to 1
if (n == 1)
{
// Count steps
int total_steps = x + (2 * y);
// Return the total number of steps
return total_steps;
}
else
return -1;
}
// Driver Code
public static void main(String s[])
{
// Given n, a and b
int n = 48;
int a = 3, b = 12;
// Function Call
System.out.println(findIfPossible(n, a, b));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program for the above approach # Function to check if it is possible # to convert a number N to 1 by a minimum # use of the two operations def FindIfPossible(n, a, b): # For the Case b % a != 0 if (b % a) != 0: # Check if n equal to 1 if n == 1: return 0 # Check if n is not # divisible by b elif (n % b) != 0: return -1 else: return int(n / b) # For the Case b % a == 0 # Initialize a variable 'c' c = b / a x = 0 y = 0 # Loop until n is divisible by b while (n % b == 0): n /= b # Count number of divisions x += 1 # Loop until n is divisible by c while (n % c == 0): n /= c # Count number of operations y += 1 # Check if n is reduced to 1 if n == 1: # Count steps total_steps = x + 2 * y # Return the total number of steps return total_steps else: return -1 # Driver code # Given n, a and b n = 48 a = 3 b = 12 print(FindIfPossible(n, a, b)) # This code is contributed by virusbuddah_
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if it is possible
// to convert a number N to 1 by a minimum
// use of the two operations
static int findIfPossible(int n, int a, int b)
{
// For the Case b % a != 0
if (b % a != 0)
{
// Check if n equal to 1
if (n == 1)
return 0;
// Check if n is not
// divisible by b
else if (n % b != 0)
return -1;
else
return (int)n / b;
}
// For the Case b % a == 0
// Initialize a variable 'c'
int c = b / a;
int x = 0, y = 0;
// Loop until n is divisible by b
while (n % b == 0)
{
n = n / b;
// Count number of divisions
x++;
}
// Loop until n is divisible by c
while (n % c == 0)
{
n = n / c;
// Count number of operations
y++;
}
// Check if n is reduced to 1
if (n == 1)
{
// Count steps
int total_steps = x + (2 * y);
// Return the total number of steps
return total_steps;
}
else
return -1;
}
// Driver Code
public static void Main()
{
// Given n, a and b
int n = 48;
int a = 3, b = 12;
// Function call
Console.WriteLine(findIfPossible(n, a, b));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program for the above approach
// Function to check if it is possible
// to convert a number N to 1 by a minimum
// use of the two operations
function findIfPossible(n, a, b)
{
// For the Case b % a != 0
if (b % a != 0)
{
// Check if n equal to 1
if (n == 1)
return 0;
// Check if n is not
// divisible by b
else if (n % b != 0)
return -1;
else
return n / b;
}
// For the Case b % a == 0
// Initialize a variable 'c'
let c = b / a;
let x = 0, y = 0;
// Loop until n is divisible by b
while (n % b == 0)
{
n = n / b;
// Count number of divisions
x++;
}
// Loop until n is divisible by c
while (n % c == 0)
{
n = n / c;
// Count number of operations
y++;
}
// Check if n is reduced to 1
if (n == 1)
{
// Count steps
let total_steps = x + (2 * y);
// Return the total number of steps
return total_steps;
}
else
return -1;
}
// Driver Code
// Given n, a and b
let n = 48;
let a = 3, b = 12;
// Function Call
document.write(findIfPossible(n, a, b));
</script>
Producción:
3
Complejidad de tiempo: O(log (B/A))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por UtkarshPandey6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA