Definir la función
minSumDig :: Integer -> Integer |
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 |
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 = (r + 1) * 10^d - 1
where (d,r) = divMod n 9
-- 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) |
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 = (r + 1) * 10^d - 1
where (d,r) = divMod n 9
-- 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)
Se puede imprimir o compartir con
Se puede definir por recursión (aunque es menos eficiente que la fórmula directa).