Menu Close

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

José A. Alonso,

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. Responder
    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..]]
    • Responder
      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. Responder
    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. Responder
    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)
    • Responder
      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. Responder
    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.

    • Responder
      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.

      • Responder
        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. Responder
    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)))
  6. Responder
    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]]
  7. Responder
    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"

Escribe tu solución

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