# programming challenge – HackerRank – Binary tree to compute the Nth power of natural numbers that sum up to X

I’m trying to solve this challenge on HackerRank.

In short, given `x` and `n`, I have to determine how many ways I can pick numbers from the `n`th powers of the natural numbers such that their sum is `x`.

So my first reasoning was to compute the list of the `n`th powers that I need as a first step. This list is

``````list = takeWhile (<= x)  (i^n | i <- (1..))`
``````

Now `list` is the bucket from which I have to pick numbers to add up to `n`.

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 `list`:

``````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 `x`.

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.