Menor x tal que los x múltiplos de n contienen todos los dígitos
Definir la función
|
1 |
menorX :: Integer -> Integer |
tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que
|
1 2 3 4 5 6 |
92 contiene [2,9] 92 y 92×2 contienen [1,2,4,8,9] 92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9] 92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9] 92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9] 92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9] |
Otros ejemplos
|
1 2 3 4 5 6 7 8 9 |
menorX 92 == 6 menorX 2967 == 3 menorX 266 == 4 menorX 18 == 5 menorX 2 == 45 menorX 125 == 72 menorX 1234567890 == 1 maximum [menorX n | n <- [1..3000]] == 72 minimum [menorX n | n <- [1..3000]] == 3 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
import Data.List ((\\)) -- 1ª definición -- ============= menorX :: Integer -> Integer menorX n = head [x | x <- [1..] , [0..9] `contenido` digitosMultiplos n x] contenido :: Eq a => [a] -> [a] -> Bool contenido xs ys = all (`elem` ys) xs digitosMultiplos :: Integer -> Integer -> [Integer] digitosMultiplos n x = concatMap digitos [n,2*n..x*n] digitos :: Integer -> [Integer] digitos n = [read [c] | c <- show n] -- 2ª definición -- ============= menorX2 :: Integer -> Integer menorX2 n = aux [] 0 where aux xs x | [0..9] `contenido` xs = x | otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1) -- 3ª definición -- ============= menorX3 :: Integer -> Integer menorX3 n = aux ['0'..'9'] 0 where aux xs x | null xs = x | otherwise = aux (xs \\ show (n*(x+1))) (x+1) -- 4ª definición -- ============= menorX4 :: Integer -> Integer menorX4 n = aux "0123456789" 1 n where aux xs x nx | null ys = x | otherwise = aux ys (1+x) (nx+n) where ys = xs \\ show nx -- Comparación de eficiencia -- ========================= -- λ> maximum [menorX n | n <- [1..6000]] -- 72 -- (2.04 secs, 3,737,579,888 bytes) -- λ> maximum [menorX2 n | n <- [1..6000]] -- 72 -- (0.52 secs, 818,602,736 bytes) -- λ> maximum [menorX3 n | n <- [1..6000]] -- 72 -- (0.10 secs, 67,090,800 bytes) -- λ> maximum [menorX3 n | n <- [1..6000]] -- 72 -- (0.08 secs, 67,090,800 bytes) -- -- λ> maximum [menorX3 n | n <- [1..10^5]] -- 72 -- (0.81 secs, 1,044,781,216 bytes) -- λ> maximum [menorX4 n | n <- [1..10^5]] -- 72 -- (0.71 secs, 1,009,113,304 bytes) |