# Índice del menor elemento a eliminar para que la suma sea divisible por K

Definir la función

` indice :: [Int] -> Int -> Maybe Int`

tal que (indice xs k) es el índice del menor elemento a eliminar de la lista de enteros positivos xs para que la suma de los restantes sea divisible por k o Nothing, si no existe dicho elemento. Por ejemplo,

``` indice [1,8,4,1] 2 == Just 2 indice [4,6,7,5,7] 11 == Just 2 indice [4,6,7,5,7] 12 == Just 3 indice [4,6,7,5,7] 13 == Nothing indice [1..10^7] 7 == Just 5 indice [10^7,10^7-1..1] 7 == Just 9999994```

#### Soluciones

```import Test.QuickCheck import Data.List (sort) import Data.Maybe (listToMaybe)   -- 1ª solución -- ===========   indice :: [Int] -> Int -> Maybe Int indice xs k | null ys = Nothing | otherwise = Just (head ys) where ys = [i | (_,i,zs) <- sort (eliminaciones xs), sum zs `mod` k == 0]   -- (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un -- elemento de xs, i es la posición de x en xs y zs es la lista de los -- restantes elementos de xs. Por ejemplo, -- λ> eliminaciones [5,7,6,5] -- [(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])] eliminaciones :: [a] -> [(a,Int,[a])] eliminaciones xs = [(z,i,zs) | ((z,zs),i) <- zip (aux xs) [0..]] where aux [] = [] aux [x] = [(x,[])] aux (x:y:zs) = (x,y:zs) : [(v,x:vs) | (v,vs) <- aux (y:zs)]   -- 2ª solución -- ===========   indice2 :: [Int] -> Int -> Maybe Int indice2 xs k | null ys = Nothing | otherwise = Just (head ys) where d = sum xs `mod` k ys = [i | (x,i) <- sort (zip xs [0..]), x `mod` k == d]   -- 3ª solución -- ===========   indice3 :: [Int] -> Int -> Maybe Int indice3 xs k = listToMaybe ys where d = sum xs `mod` k ys = [i | (x,i) <- sort (zip xs [0..]), x `mod` k == d]   -- Comprobación de la equivalencia -- ===============================   -- La propiedad es prop_equivalencia :: [Int] -> Int -> Bool prop_equivalencia xs k = indice xs' k' == indice2 xs' k' && indice2 xs' k' == indice3 xs' k' where xs' = map ((+1) . abs) xs k' = 1 + abs k   -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests.   -- Comparación de eficiencia -- =========================   -- La comparación es -- λ> indice [1..5000] 7 -- Just 2 -- (2.82 secs, 2,458,555,104 bytes) -- λ> indice2 [1..5000] 7 -- Just 2 -- (0.01 secs, 1,991,232 bytes) -- λ> indice3 [1..5000] 7 -- Just 2 -- (0.01 secs, 1,991,072 bytes)```

#### Nuevas soluciones

• En los comentarios se pueden escribir nuevas soluciones.
• El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Medio

## 5 soluciones de “Índice del menor elemento a eliminar para que la suma sea divisible por K”

1. Rubén Muñoz Mkrtchian
```-- 1ª Definición: -- =============   indice1 :: [Int] -> Int -> Maybe Int indice1 xs k | null listaAuxiliar = Nothing | otherwise = Just (pos (minimum listaAuxiliar) xs) where listaAuxiliar = aux1 xs k (sum xs)   -- aux1 es la lista de los elementos x de xs tales que n-x es divisible por -- k. Por ejemplo, -- λ> aux1 [3,7,5,2] 2 17 -- [3,7,5]   aux1 :: [Int] -> Int -> Int -> [Int] aux1 xs k n = [x | x <- xs, mod (n-x) k == 0]   -- pos y xs es la posición del elemento y en la lista xs. Para la función -- indice1 en este caso no es necesario definir el caso base en el que y no -- pertenece a xs. Por ejemplo, -- λ> pos 4 [1..10] -- 3   pos :: Int -> [Int] -> Int pos y (x:xs) | y == x = 0 | otherwise = 1 + pos y xs   -- 2ª Definición: -- =============   indice2 :: [Int] -> Int -> Maybe Int indice2 xs k | null listaAuxiliar = Nothing | otherwise = Just (snd (minimum listaAuxiliar)) where listaAuxiliar = aux2 xs k (sum xs)   -- aux2 xs k n es la lista de pares (x,i) tales que n-x es divisible por k, -- siendo i la posición de cada elemento x que satisface dicha condición. Por -- ejemplo, -- λ> aux2 [3,7,5,2] 2 17 -- [(3,0),(7,1),(5,2)]   aux2 :: [Int] -> Int -> Int -> [(Int,Int)] aux2 xs k n = [(x,i) | (x,i) <- zip xs [0..], mod (n-x) k == 0]   -- Comparación de eficiencia: -- =========================   -- Ambas funciones tardan bastante en calcular los dos últimos ejemplos. Se -- observa además que la eficiencia de indice1 varía en gran medida en función -- de cuál sea la posición buscada, mientras que indice2 parece tener una -- eficiencia independiente de dicha posición. -- λ> indice1 [1..10^7] 7 -- Just 5 -- (10.40 secs, 3,979,876,384 bytes) -- λ> indice2 [1..10^7] 7 -- Just 5 -- (13.43 secs, 5,637,884,632 bytes) -- λ> indice1 [10^7,10^7-1..1] 7 -- Just 9999994 -- (17.01 secs, 6,244,765,128 bytes) -- λ> indice2 [10^7,10^7-1..1] 7 -- Just 9999994 -- (13.69 secs, 5,637,890,520 bytes)```
2. Joaquín Infante Rodríguez
```import Data.Maybe import Data.List   indice :: [Int] -> Int -> Maybe Int indice xs x | eliminaDivisible xs x == [] = Nothing | otherwise = Just (minimo (eliminaDivisible xs x))   eliminaDivisible :: [Int] -> Int -> [(Int,Int)] eliminaDivisible [] x = [] eliminaDivisible xs x = [(y,n) | (y,n) <- zip xs [0..], rem (sum (delete y xs)) x == 0]   minimo :: [(Int,Int)] -> Int minimo [] = (-1) minimo xs = snd (head [(y,n) | (y,n) <- xs , y== minimum (map fst xs)])```
3. Cristina Gómez Cirera
```import Data.List   indiceA4 :: [Int] -> Int -> Maybe Int indiceA4 xs k | null t = Nothing |otherwise = Just (head t) where t = indices xs k   -- indices xs k es la lista de los índices de los elementos de xs tales que al ser -- eliminados, la suma de los restantes es múltiplo de k -- λ> indices [4,6,7,5,7] 11 -- [2,4] indices xs k = [i | (x,i) <- ys ,(t-x) `mod`k == 0] where t = sumaConPatron xs ys = sort (zip xs [0..])   -- sumaConPatron xs es la suma de la lista xs, calculándola por la fórmula de la -- progresión aritmética en caso de que se pueda -- λ> sumaConPatron [1..10^7] -- 50000005000000 sumaConPatron xs | x:y:ys == [x,y..z] = (x + z)*(length xs) `div` 2 | otherwise = sum xs where (x:y:ys) = xs z = last xs```
• José A. Alonso

La definición es incorrecta. Por ejemplo,

```λ> indice [1] 1 *** Exception: Irrefutable pattern failed for pattern x : y : ys```
4. Alejandro García Alcaide
```-- La funcion quedaria: indice :: [Int] -> Int -> Maybe Int indice xs k | not (algunoDivisible ys k) = Nothing | otherwise = Just (posicion (maximum (listaDivisibles ys k)) ys) where ys = sumaCombinaciones xs       -- La funcion posicion x xs da el lugar en el que se encuentra el elemento x en -- la lista xs. Por ejemplo: -- posicion 8 [1..8] == 7   posicion :: Int -> [Int] -> Int posicion k (x:xs) | k == x = 0 | otherwise = 1 + posicion k xs     -- La funcion algunoDivisible verifica si algun elemento de la lista es -- divisible entre y. La funcion listaDivisibles toma ese elemento. -- algunoDivisible [1..5] 2 == True -- listaDivisibles [1..5] 2 == [2,4]   listaDivisibles :: [Int] -> Int -> [Int] listaDivisibles [] _ = [] listaDivisibles (x:xs) y | mod x y == 0 = x :(listaDivisibles xs y) | otherwise = listaDivisibles xs y     algunoDivisible [] _ = False algunoDivisible (x:xs) y | mod x y == 0 = True | otherwise = algunoDivisible xs y   -- Con sumaCombinaciones, por su parte, obtenemos la suma de los elementos de las distintas -- listas formadas con combinaciones. sumaCombinaciones :: [Int] -> [Int] sumaCombinaciones xs = map sum (combinaciones xs)     -- Por otro lado, la funcion combinaciones nos da las distintas listas que se pueden forman -- quitando un elemento de la lista original xs. Por ejemplo: -- combinaciones [1..4] == [[2,3,4],[1,3,4],[1,2,4],[1,2,3]] combinaciones :: [a] -> [[a]] combinaciones xs = [elimina n xs | n <- [1..p]] where p = length xs   -- Por ultimo, la funcion elimina n xs elimina el n-esimo elemento de la lista xs. Por -- ejemplo: -- elimina 5 [1..7] == [1,2,3,4,6,7] -- elimina 3 [4..8] == [4,5,7,8] elimina :: (Eq t, Num t) => t -> [a] -> [a] elimina _ [] = [] elimina n (x:xs) | n == 1 = xs | otherwise = x: elimina (n-1) xs```

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