Menu Close

Elementos con su doble en el conjunto

Definir la función

   conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

   conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
   conDoble [2, 4, 8, 10]               ==  [2,4]
   conDoble [7, 5, 11, 13, 1, 3]        ==  []
   length (conDoble4 [1..10^6])         ==  500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Soluciones

import Data.List (intersect, sort)
import qualified Data.Set as S
 
-- 1ª Definición
conDoble :: [Int] -> [Int]
conDoble xs =
  [x | x <- xs, 2 * x `elem` xs]
 
-- 2ª Definición
conDoble2 :: [Int] -> [Int]
conDoble2 xs = aux (sort xs)
  where aux [] = []
        aux (y:ys) | 2 * y `elem` xs = y : aux ys
                   | otherwise       = aux ys
 
-- 3ª definición
conDoble3 :: [Int] -> [Int]
conDoble3 xs =
  sort (map (`div` 2) (xs `intersect` (map (*2) xs)))
 
-- 4ª definición
conDoble4 :: [Int] -> [Int]
conDoble4 xs =
  S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))
  where ys = S.fromList xs
 
-- Comparación de eficiencia
--    λ> length (conDoble [1..10^4])
--    5000
--    (3.27 secs, 0 bytes)
--    λ> length (conDoble2 [1..10^4])
--    5000
--    (3.42 secs, 0 bytes)
--    λ> length (conDoble3 [1..10^4])
--    5000
--    (4.78 secs, 0 bytes)
--    λ> length (conDoble4 [1..10^4])
--    5000
--    (0.02 secs, 0 bytes)

9 soluciones de “Elementos con su doble en el conjunto

  1. Daniel
    conDoble :: [Int] -> [Int]
    conDoble xs = [x | x <- xs , elem (2*x) xs]
  2. marmerzaf
    conDoble :: [Int] -> [Int]
     
    conDoble [] = []
    conDoble (x:xs)  | 2*x `elem` xs = x : conDoble xs
                     | otherwise =  conDoble xs
  3. paumacpar
    import Data.Set
     
    conDoble :: [Int] -> [Int]
    conDoble xs = aux xs (fromList xs) []
      where aux [] c ys = ys 
            aux (x:xs) c ys | member (2*x) c = aux xs c (x:ys)
                            | otherwise = aux xs c ys
  4. marlobrip
    conDoble :: [Int] -> [Int]
    conDoble xs = [ x | x <- xs , 2*x `elem` xs]
  5. enrnarbej
    import qualified Data.Set as S
     
    conDoble :: [Int] -> [Int]
    conDoble xs = (S.toList . S.intersection b . S.fromList) xs
                where
                 a = filter even xs
                 b = (S.fromList . map (`div` 2)) a
  6. albcercid
     
    conDoble :: [Int] -> [Int]                
    conDoble xs = filter (x -> S.member (2*x) t) xs
         where t = S.fromList (filter even xs)
  7. Miguel Ibáñez (migibagar)
    conDoble :: [Int] -> [Int]
    conDoble xs = aux xs xs []
      where aux _  [] zs     = zs
            aux ys (x:xs) zs | prop x ys  =  aux ys xs ((x `div` 2) : zs)
                             | otherwise  =  aux ys xs zs
     
    prop :: Int -> [Int] -> Bool
    prop x xs = a `elem` xs && b == 0
      where (a,b) = quotRem x 2
     
    -- Muy poco eficiente
  8. natmarmar2
    conDoble :: [Int] -> [Int]
    conDoble [] = []
    conDoble xs = [ x | x <- xs , y <- xs , y == 2*x]

Escribe tu solución

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