# Menor x tal que los x múltiplos de n contienen todos los dígitos

Definir la función

` 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

``` 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

``` 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

```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)```
Medio

## 14 soluciones de “Menor x tal que los x múltiplos de n contienen todos los dígitos”

1. angruicam1
```import Data.List (sort,nub) import Data.Maybe (fromJust)   menorX :: Integer -> Integer menorX n = toInteger . fromJust \$ lookup “0123456789” [(sort . nub . concat . map show . take m \$ iterate (+n) n,m) | m <- [1..]]```
• anddonram

Me has servido de inspiración para poder hacerlo.
Solo un comentario, probablemente lookup sea O(n) ya que es una lista y no un diccionario. length también es O(n) y ya que tiene que contener los 10 elementos distintos (por nub), podemos aprovecharnos de eso y ahorrarnos el sort.

```import Data.List import Data.Maybe menorX :: Integer -> Integer menorX n= fromMaybe 0 \$ find (x-> (length \$ nub \$ concat (map show [n,2*n..x*n]) ) == 10) [1..]```
2. jaibengue
```import Data.List (sort)   menorX :: Integer -> Integer menorX n = aux 1 [] where aux m xs | xs == ['0'..'9'] = (m-1) | otherwise = aux (m+1) (aux2 (show (m*n)) xs) where aux2 [] xs = sort xs aux2 (y:ys) xs | y `elem` xs = aux2 ys xs | otherwise = aux2 ys (y:xs)```
3. pabhueacu
```menorX :: Integer -> Integer menorX x = contiene [] x 1   contiene :: [Char] -> Integer -> Integer -> Integer contiene xs n y | length xs == 10 = y-1 | otherwise = contiene (sort.nub \$ xs ++ show (n*y)) n (y+1)```
• jaibengue

Buena definición, mejor si le quitas el sort que no lo necesitas y lo metes como función auxiliar de menorX para no cargar con la variable n en el argumento.

```import Data.List(nub)   menorX :: Integer -> Integer menorX x = contiene [] 1 where contiene xs y | length xs == 10 = y-1 | otherwise = contiene (nub \$ xs ++ show (x*y)) (y+1)```
4. jorcatote
```  menorX :: Integer -> Integer menorX = aux "0123456789" [1..]   aux :: String -> [Integer] -> Integer -> Integer aux xs ys n | m == [] = 1 | otherwise = 1 + aux m (tail ys) n where m = filter (`notElem` (show (n* head ys))) xs```

Creo que es algo más eficiente que el resto.

• angruicam1

Buenas, puedes hacer tu función aún más eficiente si tomas ys como (y:ys) y así te ahorras el usar head y tail. También puedes usar la función `(\\)` de Data.List para hacer más eficiente el cálculo de m. Quedaría tal que así:

```import Data.List (())   menorX :: Integer -> Integer menorX = aux "0123456789" [1..] where aux :: String -> [Integer] -> Integer -> Integer aux xs (y:ys) n | m == [] = 1 | otherwise = 1 + aux m ys n where m = xs show (n*y)   -- Comparación de la eficiencia: -- λ> maximum [menorX n | n <- [1..4000000]] -- 72 -- (56.42 secs, 34,850,866,600 bytes) -- λ> maximum [menorX2 n | n <- [1..4000000]] -- 72 -- (90.64 secs, 24,395,032,848 bytes)```

Donde menorX2 es tu función.

• jaibengue

Muy buena!
Estaba pensando que quizá se podría mejorar la eficiencia de esta manera:

```import Data.List ((\))   menorX :: Integer -> Integer menorX n = aux "0123456789" n where aux :: String -> Integer -> Integer aux xs u | m == [] = 1 | otherwise = 1 + aux m (u+n) where m = xs \ show u```

Dejando así la lista infinita [1..] fuera de la definición y en lugar de hacer el producto (`n*y`) cada vez que simplemente sumara n al anterior.
Sin embargo esta mejora no resulta eficiente ya que solo se usa el producto hasta `72*n` como mucho, y calcular tan pocos productos y tan pequeños no le resulta costoso al ordenador.

5. carriomon1
```import Data.List import Data.Char   menorX :: Integer -> Integer menorX x = head [toInteger n | n <- [1..], listaDigitos (take n (multiplos x)) == 0123456789]   multiplos :: Integer -> [Integer] multiplos n = [n*b | b <- [1..]]   listaDigitos :: [Integer] -> Integer listaDigitos xs = read \$ nub(sort(concat(map (show) xs)))```
• guicabgod

Falla para (menorX 1) que da 9 en lugar de 10.

6. alvblamol
```menorX :: Integer -> Integer menorX n = fromIntegral (head [x | x <-[0..] , contieneTodosDigitos (digitosLista (take x (multiplos n)))])   multiplos n = [n*x | x <- [1..]]   digitos n | n < 10 = [n] | otherwise = (mod n 10) : (digitos (div n 10))   digitosLista [] = [] digitosLista (x:xs) = (digitos x) ++ digitosLista xs   contieneTodosDigitos xs = and [elem x xs | x <- [1..9]]```
• guicabgod

Falla para (menorX 1) que da 9 en lugar de 10.

7. agumaragu1
```  menorX :: Integer -> Integer menorX n = aux n 1 [] where aux n m s | check s = m-1 | otherwise = aux n (m+1) (show(n*m)++s)   check :: [Char] -> Bool check st = all (`elem` st) "0123456789"```
• guicabgod

Se puede eliminar el primer argumento de la función aux.

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