Dados los números enteros N, K, X e Y. La tarea es encontrar el número máximo posible de N dígitos en K pasos a partir de 0. Usando las operaciones que se indican a continuación:
- Incrementar el valor por X, o
- Multiplica el valor con Y
Ejemplos:
Entrada: N = 2, K = 5, X = 2, Y = 3
Salida: 72
Explicación: La secuencia sería {0->2->6->8->24->72}Entrada: N = 2, K = 10, X = 2, Y = 3
Salida: 98
Explicación: La secuencia sería
{0 -> 0 -> 0 -> 2 -> 6 -> 8 -> 10 -> 30 -> 32 -> 96 -> 98}.
Tenga en cuenta que la secuencia 0 mencionada anteriormente se multiplica por 3 dos veces.
Otra secuencia posible es
{0 -> 0 -> 2 -> 4 -> 6 -> 8 -> 10 -> 30 -> 32 -> 96 -> 98}.Entrada: N = 3 y K = 4
Salida: -1
Explicación: No es posible crear un número de 3 dígitos en 4 pasos
Enfoque: El problema se puede resolver utilizando el concepto de recursividad . Siga los pasos que se mencionan a continuación:
- Para cada paso recursivo, salga de la llamada recursiva cuando:
- Si el número de pasos tomados es mayor que K , entonces se debe detener la recursividad.
- Si el conteo de dígitos del número actual excede N , entonces no hay necesidad de buscar en esa rama.
- Si el número actual llega a ser igual al número máximo de N dígitos que se puede generar, entonces no hay necesidad de más procesamiento. Reducirá el número de llamadas extra recursivas.
- El número máximo posible de N dígitos que se puede generar en cualquier momento es (10 N – 1) .
- Ahora llame recursivamente al método con el número actual incrementado en X y el paso actual incrementado en 1 .
- Realice otra llamada recursiva con el número actual multiplicado por Y y el paso actual incrementado en 1 .
- Almacene ambos resultados en una variable.
- En cualquier punto de recursión, devuelve el máximo de los dos resultados almacenados en la variable.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function for generating largest
// N-digit number in K-steps.
int largestNDigitNumber(int N, int currentStep,
int K, int X, int Y,
int currentValue)
{
// Further processing is useless
// ifcCurrent value already becomes equal
// to largest N-digit number that
// can be generated
if (currentValue == pow(10, N) - 1)
return currentValue;
// Return 0 steps taken is greater than K
// and also if N or K equal to Zero.
if (currentStep > K || N < 1 || K < 1)
return 0;
// currentValue exceeds maxValue,
// so there is no need to
// keep searching on that branch.
if (currentValue >= pow(10, N))
return 0;
// Recursive calls
int result2 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue + X);
int result1 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue * Y);
// If both the results are zero
// it means maximum is reached.
if (result1 == 0 && result2 == 0)
return currentValue;
// Checking for maximum of the two results.
return result1 > result2 ? result1 : result2;
}
// Driver code
int main()
{
int N = 2, K = 10, X = 2, Y = 3;
int largest = largestNDigitNumber(
N, 0, K, X, Y, 0);
// Checking whether the returned result
// is a N-digit number or not.
if (largest < pow(10, (N - 1))) {
cout << ("-1");
}
else
cout << largest;
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG
{
// Function for generating largest
// N-digit number in K-steps.
static int largestNDigitNumber(int N, int currentStep,
int K, int X, int Y,
int currentValue)
{
// Further processing is useless
// ifcCurrent value already becomes equal
// to largest N-digit number that
// can be generated
if (currentValue == Math.pow(10, N) - 1)
return currentValue;
// Return 0 steps taken is greater than K
// and also if N or K equal to Zero.
if (currentStep > K || N < 1 || K < 1)
return 0;
// currentValue exceeds maxValue,
// so there is no need to
// keep searching on that branch.
if (currentValue >= Math.pow(10, N))
return 0;
// Recursive calls
int result2 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue + X);
int result1 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue * Y);
// If both the results are zero
// it means maximum is reached.
if (result1 == 0 && result2 == 0)
return currentValue;
// Checking for maximum of the two results.
return result1 > result2 ? result1 : result2;
}
// Driver code
public static void main(String[] args)
{
int N = 2, K = 10, X = 2, Y = 3;
int largest = largestNDigitNumber(
N, 0, K, X, Y, 0);
// Checking whether the returned result
// is a N-digit number or not.
if (largest < Math.pow(10, (N - 1))) {
System.out.print("-1");
}
else
System.out.print(largest);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code for the above approach
# Function for generating largest
# N-digit number in K-steps.
def largestNDigitNumber(N, currentStep, K, X, Y, currentValue):
# Further processing is useless
# ifcCurrent value already becomes equal
# to largest N-digit number that
# can be generated
if (currentValue == 10 ** N - 1):
return currentValue
# Return 0 steps taken is greater than K
# and also if N or K equal to Zero.
if (currentStep > K or N < 1 or K < 1):
return 0
# currentValue exceeds maxValue,
# so there is no need to
# keep searching on that branch.
if (currentValue >= 10 ** N):
return 0
# Recursive calls
result2 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue + X)
result1 = largestNDigitNumber( N, currentStep + 1, K, X, Y, currentValue * Y)
# If both the results are zero
# it means maximum is reached.
if (result1 == 0 and result2 == 0):
return currentValue
# Checking for maximum of the two results.
return result1 if result1 > result2 else result2
# Driver code
N = 2
K = 10
X = 2
Y = 3
largest = largestNDigitNumber(N, 0, K, X, Y, 0)
# Checking whether the returned result
# is a N-digit number or not.
if (largest < 10 ** (N - 1)):
print("-1")
else:
print(largest)
# This code is contributed by Saurabh Jaiswal.
C#
// C# code to implement the approach
using System;
class GFG {
// Function for generating largest
// N-digit number in K-steps.
static int largestNDigitNumber(int N, int currentStep,
int K, int X, int Y,
int currentValue)
{
// Further processing is useless
// ifcCurrent value already becomes equal
// to largest N-digit number that
// can be generated
if (currentValue == Math.Pow(10, N) - 1)
return currentValue;
// Return 0 steps taken is greater than K
// and also if N or K equal to Zero.
if (currentStep > K || N < 1 || K < 1)
return 0;
// currentValue exceeds maxValue,
// so there is no need to
// keep searching on that branch.
if (currentValue >= Math.Pow(10, N))
return 0;
// Recursive calls
int result2 = largestNDigitNumber(
N, currentStep + 1, K, X, Y, currentValue + X);
int result1 = largestNDigitNumber(
N, currentStep + 1, K, X, Y, currentValue * Y);
// If both the results are zero
// it means maximum is reached.
if (result1 == 0 && result2 == 0)
return currentValue;
// Checking for maximum of the two results.
return result1 > result2 ? result1 : result2;
}
// Driver code
public static void Main(string[] args)
{
int N = 2, K = 10, X = 2, Y = 3;
int largest = largestNDigitNumber(N, 0, K, X, Y, 0);
// Checking whether the returned result
// is a N-digit number or not.
if (largest < Math.Pow(10, (N - 1))) {
Console.Write("-1");
}
else
Console.Write(largest);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function for generating largest
// N-digit number in K-steps.
function largestNDigitNumber(N, currentStep,
K, X, Y,
currentValue)
{
// Further processing is useless
// ifcCurrent value already becomes equal
// to largest N-digit number that
// can be generated
if (currentValue == Math.pow(10, N) - 1)
return currentValue;
// Return 0 steps taken is greater than K
// and also if N or K equal to Zero.
if (currentStep > K || N < 1 || K < 1)
return 0;
// currentValue exceeds maxValue,
// so there is no need to
// keep searching on that branch.
if (currentValue >= Math.pow(10, N))
return 0;
// Recursive calls
let result2 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue + X);
let result1 = largestNDigitNumber(
N, currentStep + 1, K, X, Y,
currentValue * Y);
// If both the results are zero
// it means maximum is reached.
if (result1 == 0 && result2 == 0)
return currentValue;
// Checking for maximum of the two results.
return result1 > result2 ? result1 : result2;
}
// Driver code
let N = 2, K = 10, X = 2, Y = 3;
let largest = largestNDigitNumber(
N, 0, K, X, Y, 0);
// Checking whether the returned result
// is a N-digit number or not.
if (largest < Math.pow(10, (N - 1))) {
document.write("-1");
}
else
document.write(largest);
// This code is contributed by Potta Lokesh
</script>
Producción
98
Tiempo Complejidad: O(2 K )
Espacio Auxiliar: O(1)