Mayor número borrando k dígitos

Definir la función

tal que (mayorBorrando k n) es el mayor número obtenido borrando k dígitos de n (se supone que n tiene más de k dígitos). Por ejemplo,

Soluciones

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

7 Comentarios

    1. La solución de María da respuestas erróneas, Por ejemplo,

      pero debería de dar 20.

    1. En el siguiente ejemplo, hay al menos dos nueves entre el primer grupo que puede quitarse o mantenerse, es decir, mejor empezar con 99 que con 97, por lo que la solución no parece correcta:

  1. Diría que puede implementarse con coste en media algo como O(log n) (sí, no hace falta mirar todos los dígitos de entrada) y seguro con coste lineal en el número de dígitos. La siguiente implementación no es eficiente para que sea más legible (ej. está partiendo en los dígitos máximos del rango pero eso puede predecirse). En todo caso, pueden «optimizarse» números con centenas de miles de dígitos:

    1. Perdiendo legibilidad pero en tiempo (casi) lineal (para serlo del todo hay que guardar los máximos para cada paso):

Leave a Reply to j0sejuanCancel reply