-- http://www.codewars.com/kata/5547cc7dcad755e480000004
module Codewars.Kata.RemovNB where

import Data.Tuple

-- if (a, b) is a removed pair then a*b+a+b = 1+..+n
-- and (a+1)(b+1) = 1+..+n + 1 =: s
-- looping over divisors of s allows to restore
-- all possible a and b in the effective way
removNb :: Integer-> [(Integer, Integer)]
removNb n = ds ++ reverse (map swap ds) where
  s = 1 + n * (n + 1) `div` 2
  isqrt = floor . sqrt . fromInteger
  ds = [(d - 1, s `div` d - 1) | d <- [n `div` 2 .. isqrt s], s `mod` d == 0]
