We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Divisible Sum Pairs
  5. Discussions

Divisible Sum Pairs

  • jmcparland
     + 0 comments

    Haskell:

    The easy, brute force way (solve) and the better, single-pass way (solve2).

    module Main where

import qualified Data.IntMap as M

solve :: Int -> [Int] -> Int
solve k ar = length [(i, j) | i <- [0 .. length ar - 2], j <- [i + 1 .. length ar - 1], (ar !! i + ar !! j) `mod` k == 0]

go :: Int -> [Int] -> M.IntMap Int -> Int -> Int
go _ [] _ count = count
go target (x : xs) m count = go target xs (M.insertWith (+) (x `mod` target) 1 m) (count + M.findWithDefault 0 ((target - x) `mod` target) m)

solve2 :: Int -> [Int] -> Int
solve2 k ar = go k ar M.empty 0

main :: IO ()
main = do
    [_, k] <- map read . words <$> getLine :: IO [Int]
    ar <- map read . words <$> getLine :: IO [Int]
    print $ solve2 k ar