Count ways to express a number as sum of powers
Last Updated : 22 Nov, 2023
Given two integers x and n, we need to find number of ways to express x as sum of n-th powers of unique natural numbers. It is given that 1 <= n <= 20.
Examples:
Input : x = 100 n = 2 Output : 3 Explanation: There are three ways to express 100 as sum of natural numbers raised to power 2. 100 = 10^2 = 8^2+6^2 = 1^2+3^2+4^2+5^2+7^2 Input : x = 100 n = 3 Output : 1 Explanation : The only combination is, 1^3 + 2^3 + 3^3 + 4^3
We use recursion to solve the problem. We first check one by one that the number is included in summation or not.
C++ // C++ program to count number of ways // to express x as sum of n-th power // of unique natural numbers. #include <bits/stdc++.h> using namespace std; // num is current num. int countWaysUtil(int x, int n, int num) { // Base cases int val = (x - pow(num, n)); if (val == 0) return 1; if (val < 0) return 0; // Consider two possibilities, num is // included and num is not included. return countWaysUtil(val, n, num + 1) + countWaysUtil(x, n, num + 1); } // Returns number of ways to express // x as sum of n-th power of two. int countWays(int x, int n) { return countWaysUtil(x, n, 1); } // Driver code int main() { int x = 100, n = 2; cout << countWays(x, n); return 0; } // Java program to count number of ways // to express x as sum of n-th power // of unique natural numbers. public class GFG { // num is current num. static int countWaysUtil(int x, int n, int num) { // Base cases int val = (int) (x - Math.pow(num, n)); if (val == 0) return 1; if (val < 0) return 0; // Consider two possibilities, num is // included and num is not included. return countWaysUtil(val, n, num + 1) + countWaysUtil(x, n, num + 1); } // Returns number of ways to express // x as sum of n-th power of two. static int countWays(int x, int n) { return countWaysUtil(x, n, 1); } // Driver code public static void main(String args[]) { int x = 100, n = 2; System.out.println(countWays(x, n)); } } // This code is contributed by Sumit Ghosh # Python program to count number of ways # to express x as sum of n-th power # of unique natural numbers. # num is current num. def countWaysUtil(x,n,num): # Base cases val = (x - pow(num, n)) if (val == 0): return 1 if (val < 0): return 0 # Consider two possibilities, num is # included and num is not included. return countWaysUtil(val, n, num + 1) +\ countWaysUtil(x, n, num + 1) # Returns number of ways to express # x as sum of n-th power of two. def countWays(x,n): return countWaysUtil(x, n, 1) # Driver code x = 100 n = 2 print(countWays(x, n)) # This code is contributed # by Anant Agarwal.
// C# program to count number of ways // to express x as sum of n-th power // of unique natural numbers. using System; public class GFG { // num is current num. static int countWaysUtil(int x, int n, int num) { // Base cases int val = (int) (x - Math.Pow(num, n)); if (val == 0) return 1; if (val < 0) return 0; // Consider two possibilities, // num is included and num is // not included. return countWaysUtil(val, n, num + 1) + countWaysUtil(x, n, num + 1); } // Returns number of ways to express // x as sum of n-th power of two. static int countWays(int x, int n) { return countWaysUtil(x, n, 1); } // Driver code public static void Main() { int x = 100, n = 2; Console.WriteLine(countWays(x, n)); } } // This code is contributed by vt_m. <script> // JavaScript program to count number of ways // to express x as sum of n-th power // of unique natural numbers. // num is current num. function countWaysUtil(x, n, num) { // Base cases let val = (x - Math.pow(num, n)); if (val == 0) return 1; if (val < 0) return 0; // Consider two possibilities, num is // included and num is not included. return countWaysUtil(val, n, num + 1) + countWaysUtil(x, n, num + 1); } // Returns number of ways to express // x as sum of n-th power of two. function countWays(x, n) { return countWaysUtil(x, n, 1); } // Driver code let x = 100, n = 2; document.write(countWays(x, n)); // This code is contributed by Mayank Tyagi </script> <?php // PHP program to count number of ways // to express x as sum of n-th power // of unique natural numbers. // num is current num. function countWaysUtil($x, $n, $num) { // Base cases $val = ($x - pow($num, $n)); if ($val == 0) return 1; if ($val < 0) return 0; // Consider two possibilities, num is // included and num is not included. return (countWaysUtil($val, $n, $num + 1) + countWaysUtil($x, $n, $num + 1)); } // Returns number of ways to express // x as sum of n-th power of two. function countWays($x, $n) { return countWaysUtil($x, $n, 1); } // Driver code $x = 100; $n = 2; echo(countWays($x, $n)); // This code is contributed by Ajit. ?> Output:
3
Time Complexity: O(2 ^ pow(x^(1/n)))
Auxiliary Space: O(pow(x^(1/n))
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile