Ir al contenido principal

Menor con suma de dígitos dada

Definir la función

minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

minSumDig 1   ==  1
minSumDig 12  ==  39
minSumDig 21  ==  399
(length . show . minSumDig) (3*10^5)  ==  33334
(length . show . minSumDig) (3*10^6)  ==  333334
(length . show . minSumDig) (3*10^7)  ==  3333334
(length . show . minSumDig) (4*10^7)  ==  4444445
(length . show . minSumDig) (5*10^7)  ==  5555556

Soluciones

import Data.List (genericIndex)

-- 1ª definición
-- =============

minSumDig1 :: Integer -> Integer
minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]

sumaDigitos :: Integer -> Integer
sumaDigitos n | n < 10    = n
              | otherwise = y + sumaDigitos x
  where (x, y) = divMod n 10

-- 2ª definición
minSumDig2 :: Integer -> Integer
minSumDig2 n | n < 10    = n
             | otherwise = 9 + 10 * minSumDig2 (n - 9)

-- 3ª definición
minSumDig3 :: Integer -> Integer
minSumDig3 n = ((n `mod` 9) + 1)*10^floor(fromIntegral n / 9) - 1

-- Comparación de eficiencia
-- =========================

--    λ> minSumDig1 46
--    199999
--    (3.21 secs, 542,721,696 bytes)
--    λ> minSumDig2 46
--    199999
--    (0.01 secs, 142,056 bytes)
--    λ> minSumDig3 46
--    199999
--    (0.01 secs, 155,984 bytes)
--
--    λ> (length . show . minSumDig2) (3*10^5)
--    33334
--    (1.79 secs, 492,200,376 bytes)
--    λ> (length . show . minSumDig3) (3*10^5)
--    33334
--    (0.11 secs, 50,119,840 bytes)