I'm trying to solve this challenge on HackerRank.
In short, given
n, I have to determine how many ways I can pick numbers from the
nth powers of the natural numbers such that their sum is
So my first reasoning was to compute the list of the
nth powers that I need as a first step. This list is
list = takeWhile (<= x) [i^n | i <- [1..]]`
list is the bucket from which I have to pick numbers to add up to
I first thought about list comprehensions, because that's how I would pick a given number of numbers from the list; for instance this is how I would generate the
sumList of the sums of any different triplets from
sumList = [x + y + z | x <- list, y <- dropWhile (<= x) list, z <- dropWhile (<= y) list]
Then I would just need to
length $ filter (== x) sumList.
However, after some thinking, I concluded that list comprehensions are not the way to go, since I don't know in advance how many numbers I have to pick from
list when attempting to sum them up to
So I thought that any possible sum corresponds to a combination of pick or not-pick while traversing the
list. This made me think of binary trees, and I eventually came up with this solution, which fails the Test Case 3 for timeout:
main :: IO() main = do [x,n] <- sequence $ replicate 2 ((read :: String -> Int) <$> getLine) print $ length $ filter (== x) $ getLeaves $ listToSumTree $ takeWhile (<= x) [i^n | i <- [1..]] data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Show) listToTreeImpl :: (Num a, Eq a) => [a] -> Tree a -> Tree a listToTreeImpl  tree = tree listToTreeImpl (l:ls) (Leaf x) = Node x (listToTreeImpl ls $ Leaf x) (listToTreeImpl ls $ Leaf (x + l)) getLeaves :: Tree a -> [a] getLeaves (Leaf a) = [a] getLeaves (Node _ (Leaf _) (Node _ _ _)) = error "this should not happen" getLeaves (Node _ (Node _ _ _) (Leaf _)) = error "this should not happen" getLeaves (Node _ left right) = getLeaves left ++ getLeaves right listToSumTree :: (Num a, Eq a) => [a] -> Tree a listToSumTree ls = listToTreeImpl ls (Leaf 0)
I can only think of
getLeaves $ listToSumTree as the only critical part of the program, since
listToSumTree constructs a full tree, which is not needed (only the leaves are), and
getLeaves traverses all the tree, only to get to the bottom layer of it.