Dado un entero N > 0 , la tarea es encontrar el máximo producto de dígitos entre números menores o iguales a N.
Ejemplos:
Entrada: N = 390
Salida: 216
El producto máximo posible viene dado por el número 389
3 * 8 * 9 = 216
Entrada: N = 432
Salida: 243
Enfoque: Este problema también se puede resolver usando el método descrito en este artículo tomando el límite inferior como 1 y el límite superior como N . Otro método para resolver este problema es mediante el uso de la recursividad. Las condiciones para la recursividad son las siguientes:
- Si N = 0 , devuelve 1 .
- Si N < 10 , devuelva N .
- De lo contrario, devuelve max(maxProd(N / 10) * (N % 10), maxProd((N / 10) – 1) * 9
En cada paso de la recursividad, se toma el último dígito o 9 para maximizar el producto del dígito.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns the maximum product of // digits among numbers less than or equal to N int maxProd(int N) { if (N == 0) return 1; if (N < 10) return N; return max(maxProd(N / 10) * (N % 10), maxProd(N / 10 - 1) * 9); } // Driver code int main() { int N = 390; cout << maxProd(N); return 0; }
Java
// Java implementation of the approach import java.io.*; class GFG { // Function that returns the maximum product of // digits among numbers less than or equal to N static int maxProd(int N) { if (N == 0) return 1; if (N < 10) return N; return Math.max(maxProd(N / 10) * (N % 10), maxProd(N / 10 - 1) * 9); } // Driver code public static void main (String[] args) { int N = 390; System.out.println (maxProd(N)); } } // This code is contributed by ajit.
Python3
# Python3 implementation of the approach # Function that returns the maximum product of # digits among numbers less than or equal to N def maxProd(N): if (N == 0): return 1 if (N < 10): return N return max(maxProd(N // 10) * (N % 10), maxProd(N // 10 - 1) * 9) # Driver code N = 390 print(maxProd(N)) # This code is contributed by mohit kumar
C#
// C# implementation of the approach using System; class GFG { // Function that returns the maximum product of // digits among numbers less than or equal to N static int maxProd(int N) { if (N == 0) return 1; if (N < 10) return N; return Math.Max(maxProd(N / 10) * (N % 10), maxProd(N / 10 - 1) * 9); } // Driver code static public void Main () { int N = 390; Console.WriteLine(maxProd(N)); } } // This code is contributed by Tushil..
PHP
<?php // PHP implementation of the approach // Function that returns the maximum product of // digits among numbers less than or equal to N function maxProd($N) { if ($N == 0) return 1; if ($N < 10) return $N; return max(maxProd((int)($N / 10)) * ($N % 10), maxProd((int)($N / 10) - 1) * 9); } // Driver code $N = 390; echo maxProd($N); // This code is contributed by Akanksha Rai ?>
Javascript
<script> // Javascript implementation of the approach // Function that returns the maximum product of // digits among numbers less than or equal to N function maxProd(N) { if (N == 0) return 1; if (N < 10) return N; return Math.max(maxProd(parseInt(N / 10)) * (N % 10), maxProd(parseInt(N / 10) - 1) * 9); } // Driver code let N = 390; document.write(maxProd(N)); // This code is contributed // by bobby </script>
216
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA