Dados dos números y N y D . Aplique cualquiera de las dos operaciones siguientes a N :
- añadir D a N
- cambie N a digitsum(N) , donde digitsum(N) es la suma de los dígitos de N
La tarea es transformar N al mínimo valor posible. Imprime el valor mínimo posible de N y el número de veces que se aplicaron las operaciones dadas (cualquiera de ellas). El número de operaciones debe ser mínimo.
Ejemplos:
Entrada: N = 2, D = 1
Salida: 1 9
Realice la operación Tipo 1 8 veces y la operación Tipo 2 1 vez
Entrada: N = 9, D = 3
Salida: 3, 2
Aplique una operación Tipo 1 primero y luego la operación Tipo 2
Prerrequisitos:
1. Raíz digital (suma digital repetida) del entero grande dado
2. Números en un rango con raíz digital dada
Enfoque:
Sea Dr(x) una función definida para el entero x como:
- Dr(x) = x, si 0 <= x <= 9
- de lo contrario, Dr(x) = Dr(Suma-de-dígitos(x))
La función Dr(x) es la raíz digital de un número x.
- Dr(a+b) = Dr(Dr(a) + Dr(b))
- Dr(ab) = Dr(Dr(a) * Dr(b))
Observación importante: El valor mínimo es siempre el mínimo sobre: Dr(N + kD) para algún número entero no negativo k.
Dr(N + kD) = Dr(Dr(N) + Dr(kD)) (1)
Ahora, Dr(kd) = Dr(Dr(k) * Dr(D))
Los posibles valores de Dr(k) son 0, 1, 2…9, dados por los números k=0, 1, 2…9
Dr(x) = Dr(Sum-of-digits(x)) (2)
- El valor mínimo de N es igual al valor mínimo de Suma de dígitos (N). Si reducimos esta respuesta una vez y le sumamos D, el valor mínimo que se puede obtener no cambiaría. Entonces, si se requiere realizar una operación de reducción y luego una operación de suma, entonces podemos hacer la operación de suma y luego la operación de reducción sin afectar las posibles raíces que podemos alcanzar. Esto es evidente a partir de la combinación de las fórmulas (1) y (2)
- Entonces, podemos hacer todas las operaciones de suma primero, todas las operaciones de reducción después y llegar a cualquier número que pueda ser alcanzado por cualquier conjunto de operaciones. Utilizando las afirmaciones anteriores, podemos probar que el valor mínimo posible es el mínimo de Dr(N + kD) donde 0 <= k <= 9.
- Para encontrar el número mínimo de pasos, tenga en cuenta que el orden relativo de las operaciones de suma y suma de dígitos afecta la respuesta. Además, tenga en cuenta que la función Suma de dígitos disminuye extremadamente rápido.
- Cualquier número <= 10 10 se convierte en un número <= 90, cualquier número <= 90 se convierte en algo <= 18 y así sucesivamente. En resumen, cualquier número se puede reducir a su raíz digital en <= 5 pasos.
- A través de esto, podemos probar que el valor de los pasos mínimos nunca puede ser superior a 15. Este es un límite superior flexible, no el exacto.
- Use el algoritmo de recursión de fuerza bruta, que en cada paso se bifurca en 2 direcciones diferentes, una x = suma de dígitos (x), la otra es x = x + D, pero solo hasta una profundidad de recursión de 15. De esta manera, nos detenemos después de explorar 2 15 formas diferentes.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to transform N to the minimum value #include <bits/stdc++.h> using namespace std; // Initialising the answer int min_val = INT_MAX; int min_steps = 0; // Function to find the digitsum int sumOfDigits(int n) { string s = to_string(n); int sum = 0; // Iterate over all digits and add them for (int i = 0; i < s.length(); i++) { sum += (s[i] - '0'); } // Return the digit su, return sum; } // Function to transform N to the minimum value void Transform(int n, int d, int steps) { // If the final value is lesser than least value if (n < min_val) { min_val = n; min_steps = steps; } // If final value is equal to least value then check // for lesser number of steps to reach this value else if (n == min_val) { min_steps = min(min_steps, steps); } // The value will be obtained in less than 15 steps as // proved so applying normal recursive operations if (steps < 15) { Transform(sumOfDigits(n), d, steps + 1); Transform(n + d, d, steps + 1); } } // Driver code int main() { int N = 9, D = 3; // Function call Transform(N, D, 0); // Print the answers cout << min_val << " " << min_steps; return 0; }
Java
// JAVA program to transform N to the minimum value import java.util.*; class GFG{ // Initialising the answer static int min_val = Integer.MAX_VALUE; static int min_steps = 0; // Function to find the digitsum static int sumOfDigits(int n) { String s = String.valueOf(n); int sum = 0; // Iterate over all digits and add them for (int i = 0; i < s.length(); i++) { sum += (s.charAt(i) - '0'); } // Return the digit su, return sum; } // Function to transform N to the minimum value static void Transform(int n, int d, int steps) { // If the final value is lesser than least value if (n < min_val) { min_val = n; min_steps = steps; } // If final value is equal to least value then check // for lesser number of steps to reach this value else if (n == min_val) { min_steps = Math.min(min_steps, steps); } // The value will be obtained in less than 15 steps as // proved so applying normal recursive operations if (steps < 15) { Transform(sumOfDigits(n), d, steps + 1); Transform(n + d, d, steps + 1); } } // Driver code public static void main(String[] args) { int N = 9, D = 3; // Function call Transform(N, D, 0); // Print the answers System.out.print(min_val+ " " + min_steps); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to transform N to the minimum value import sys; # Initialising the answer min_val = sys.maxsize; min_steps = 0; # Function to find the digitsum def sumOfDigits(n) : s = str(n); sum = 0; # Iterate over all digits and add them for i in range(len(s)) : sum += (ord(s[i]) - ord('0')); # Return the digit su, return sum; # Function to transform N to the minimum value def Transform(n, d, steps) : global min_val;global min_steps; # If the final value is lesser than least value if (n < min_val) : min_val = n; min_steps = steps; # If final value is equal to least value then check # for lesser number of steps to reach this value elif (n == min_val) : min_steps = min(min_steps, steps); # The value will be obtained in less than 15 steps as # proved so applying normal recursive operations if (steps < 15) : Transform(sumOfDigits(n), d, steps + 1); Transform(n + d, d, steps + 1); # Driver code if __name__ == "__main__" : N = 9; D = 3; # Function call Transform(N, D, 0); # Print the answers print(min_val, min_steps); # This code is contributed by Yash_R
C#
// C# program to transform N to the minimum value using System; class GFG{ // Initialising the answer static int min_val = int.MaxValue; static int min_steps = 0; // Function to find the digitsum static int sumOfDigits(int n) { string s = n.ToString(); int sum = 0; // Iterate over all digits and add them for (int i = 0; i < s.Length; i++) { sum += (s[i] - '0'); } // Return the digit su, return sum; } // Function to transform N to the minimum value static void Transform(int n, int d, int steps) { // If the final value is lesser than least value if (n < min_val) { min_val = n; min_steps = steps; } // If final value is equal to least value then check // for lesser number of steps to reach this value else if (n == min_val) { min_steps = Math.Min(min_steps, steps); } // The value will be obtained in less than 15 steps as // proved so applying normal recursive operations if (steps < 15) { Transform(sumOfDigits(n), d, steps + 1); Transform(n + d, d, steps + 1); } } // Driver code public static void Main(string[] args) { int N = 9, D = 3; // Function call Transform(N, D, 0); // Print the answers Console.Write(min_val+ " " + min_steps); } } // This code is contributed by Yash_R
Javascript
<script> // Javascript program to transform N to the minimum value // Let initialising the answer let min_val = Number.MAX_VALUE; let min_steps = 0; // Function to find the digitsum function sumOfDigits(n) { let s = n.toString(); let sum = 0; // Iterate over all digits and add them for (let i = 0; i < s.length; i++) { sum += (s[i] - '0'); } // Return the digit su, return sum; } // Function to transform N to the minimum value function Transform(n, d, steps) { // If the final value is lesser than least value if (n < min_val) { min_val = n; min_steps = steps; } // If final value is equal to least value then check // for lesser number of steps to reach this value else if (n == min_val) { min_steps = Math.min(min_steps, steps); } // The value will be obtained in less than 15 steps as // proved so applying normal recursive operations if (steps < 15) { Transform(sumOfDigits(n), d, steps + 1); Transform(n + d, d, steps + 1); } } // Driver Code let N = 9, D = 3; // Function call Transform(N, D, 0); // Print the answers document.write(min_val+ " " + min_steps); </script>
3 2
Complejidad del tiempo: