Suma de números monótonos crecientes

propuesto por josejuan

Calcular, de forma eficiente, la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente.

Enunciado
Calcular, de forma eficiente, la suma de todos los enteros positivos cuyos dígitos forman una sucesión estrictamente creciente.

En base 10, todos los números cuyos dígitos forman una sucesión estrictamente creciente (el número siguiente debe ser, forzosamente, mayor que el anterior) si aparecen los dígitos en el siguiente orden
 0123456789

entonces el 0 se puede descartar y cada dígito puede o no estar
 dígito:       123456789
 está/no está: xxxxxxxxx   (con x bit 0/1)

entonces hay 2^9 números que cumplen la propiedad.

En general, para base N, hay 2^(N-1) números que cumplen la propiedad.

Encontrar un algoritmo con coste polinómico en N (no exponencial).

NOTA: como el desafío consiste en el algoritmo propuesto y no en cálculos en una base genérica (N-ésima), puede asumirse que disponemos de un tipo numérico en dicha base, implementándolo únicamente para base 10.
Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

4 Soluciones

Dar mi solución

0votos
Suma de números monótonos crecientes en Haskell
por

josejuan

hace 6 años

Basta ver, que para un nuevo dígito que ponemos a la izquierda, podemos tener ya calculadas todas las sumas de las combinaciones de los dígitos que hemos ido agrupando a la derecha. Por ejemplo, si hemos acumulado 45, 56, 67, 78, tan sólo nos hace falta saber que son 4 nºs de 2 dígitos que suman 246; entonces, al añadir el 3, tendremos ahora 3 * 10^2 * 4 + 246 sin necesidad de ir generando y acumulando todas las combinaciones previas.

Dar mi solución