Menu Close

Menor con suma de dígitos dada

José A. Alonso,

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 = (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)
Medio
, , , , , ,

4 soluciones de “Menor con suma de dígitos dada”

  1. Responder
    angruicam1 
    minSumDig :: Integer -> Integer
minSumDig n = pred $ (succ r) * 10^d
  where (d,r) = divMod n 9
  2. Responder
    rocruimon 
    minSumDig :: Integer -> Integer
minSumDig 0 = 0 
minSumDig n = head [x | x <- [1..]
                      , sum (digitosg x) == n]
 
digitosg :: Integer -> [Integer]
digitosg n = [read [x] | x <- show n]
  3. Responder
    antgongar

    Se puede definir por recursión (aunque es menos eficiente que la fórmula directa).

    minSumDig :: Integer -> Integer
minSumDig n | n < 10    = n
            | otherwise = 9 + 10 * minSumDig (n - 9)
  4. Responder
    carbremor 
    -- Menor con suma de dígitos dada
 
 
minSumDig :: Integer -> Integer
minSumDig n = head[x | x <- [0..], digsum x == n]
 
digsum :: Integer -> Integer
digsum n | n < 10   = n
         | otherwise = last (scanl1 (+) (digitos n))
 
-- λ> digsum 5487487870
-- 58
-- (0.01 secs, 110,664 bytes)
-- λ> digsum (2548^3621)
-- 55108
-- (0.05 secs, 49,349,032 bytes)
 
digitos :: Integer -> [Integer]
digitos n = [read[d] | d <- show n]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.