The Sums of Powers – HackerRank Solution

In this post, we will solve The Sums of Powers HackerRank Solution. This problem (The Sums of Powers) is a part of HackerRank Functional Programming series.

Task

Find the number of ways that a given integer, X, can be expressed as the sum of the N^th power of unique, natural numbers.

Input Format

The first line contains an integer X.
The second line contains an integer N.

Constraints

• 1 <= X <= 1000
• 2 <= N <= 10

Output Format

Output a single integer, the answer to the problem explained above.

Sample Input 0

10
2

Sample Output 0

1

Explanation 0

If  X = 10 and N = 2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.

10 = 1² + 3²

This is the only way in which 10 can be expressed as the sum of unique squares.

Sample Input 1

100
2

Sample Output 1

3

Explanation 1

100 = 10² = 6² + 8² = 1² + 3² + 4² + 5² + 7²

Sample Input 2

100
3

Sample Output 2

1

Explanation 2

100 can be expressed as the sum of the cubes of 1, 2, 3, 4.
(1 + 8 + 27 + 64 = 100). There is no other way to express 100 as the sum of cubes.

Solution – The Sums of Powers – HackerRank Solution

Scala

import java.util.Scanner

object Solution {

  def solve(x: Int, numbers: List[Int]): Int = if (x < 0) 0 else if (x == 0) 1 else {
    numbers match {
      case Nil => 0
      case c :: cs => solve(x - c, cs) + solve(x, cs)
    }
  }

  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val x = sc.nextInt
    val n = sc.nextInt

    sc.close()

    val numbers = LazyList.from(1).map(i => BigInt(i).pow(n)).takeWhile(_ <= x).map(_.toInt).toList

    println(solve(x, numbers))
  }
}

Note: This problem (The Sums of Powers) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.