Dados dos números x y n, encuentre un número de formas en que x puede expresarse como la suma de la n-ésima potencia de números naturales únicos.
Ejemplos:
Entrada: x = 10, n = 2
Salida: 1
Explicación: 10 = 1 2 + 3 2 , Por lo tanto, total 1 posibilidadEntrada: x = 100, n = 2
Salida: 3 Explicación: 100 = 10 2
O 6 2 + 8 2 O 1 2 + 3 2 + 4 2 + 5 2 + 7 2 Por lo tanto, un total de 3 posibilidades
La idea es sencilla. Iteramos a través de todos los números a partir de 1. Para cada número, probamos recursivamente todos los números mayores y, si podemos encontrar la suma, incrementamos el resultado.
C++
// C++ program to count number of ways any // given integer x can be expressed as n-th // power of unique natural numbers. #include <bits/stdc++.h> using namespace std; // Function to calculate and return the // power of any given number int power(int num, unsigned int n) { if (n == 0) return 1; else if (n % 2 == 0) return power(num, n / 2) * power(num, n / 2); else return num * power(num, n / 2) * power(num, n / 2); } // Function to check power representations recursively int checkRecursive(int x, int n, int curr_num = 1, int curr_sum = 0) { // Initialize number of ways to express // x as n-th powers of different natural // numbers int results = 0; // Calling power of 'i' raised to 'n' int p = power(curr_num, n); while (p + curr_sum < x) { // Recursively check all greater values of i results += checkRecursive(x, n, curr_num + 1, p + curr_sum); curr_num++; p = power(curr_num, n); } // If sum of powers is equal to x // then increase the value of result. if (p + curr_sum == x) results++; // Return the final result return results; } // Driver Code. int main() { int x = 10, n = 2; cout << checkRecursive(x, n); return 0; }
Java
// Java program to count number of ways any // given integer x can be expressed as n-th // power of unique natural numbers. class GFG { // Function to calculate and return the // power of any given number static int power(int num, int n) { if (n == 0) return 1; else if (n % 2 == 0) return power(num, n / 2) * power(num, n / 2); else return num * power(num, n / 2) * power(num, n / 2); } // Function to check power representations recursively static int checkRecursive(int x, int n, int curr_num, int curr_sum) { // Initialize number of ways to express // x as n-th powers of different natural // numbers int results = 0; // Calling power of 'i' raised to 'n' int p = power(curr_num, n); while (p + curr_sum < x) { // Recursively check all greater values of i results += checkRecursive(x, n, curr_num + 1, p + curr_sum); curr_num++; p = power(curr_num, n); } // If sum of powers is equal to x // then increase the value of result. if (p + curr_sum == x) results++; // Return the final result return results; } // Driver Code. public static void main(String[] args) { int x = 10, n = 2; System.out.println(checkRecursive(x, n, 1, 0)); } } // This code is contributed by mits
Python3
# Python3 program to count number of ways any # given integer x can be expressed as n-th # power of unique natural numbers. # Function to calculate and return the # power of any given number def power(num, n): if(n == 0): return 1 elif(n % 2 == 0): return power(num, n // 2) * power(num, n // 2) else: return num * power(num, n // 2) * power(num, n // 2) # Function to check power representations recursively def checkRecursive(x, n, curr_num=1, curr_sum=0): # Initialize number of ways to express # x as n-th powers of different natural # numbers results = 0 # Calling power of 'i' raised to 'n' p = power(curr_num, n) while(p + curr_sum < x): # Recursively check all greater values of i results += checkRecursive(x, n, curr_num + 1, p + curr_sum) curr_num = curr_num + 1 p = power(curr_num, n) # If sum of powers is equal to x # then increase the value of result. if(p + curr_sum == x): results = results + 1 # Return the final result return results # Driver Code. if __name__ == '__main__': x = 10 n = 2 print(checkRecursive(x, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to count number of ways any // given integer x can be expressed as // n-th power of unique natural numbers. using System; class GFG { // Function to calculate and return // the power of any given number static int power(int num, int n) { if (n == 0) return 1; else if (n % 2 == 0) return power(num, n / 2) * power(num, n / 2); else return num * power(num, n / 2) * power(num, n / 2); } // Function to check power // representations recursively static int checkRecursive(int x, int n, int curr_num, int curr_sum) { // Initialize number of ways to express // x as n-th powers of different natural // numbers int results = 0; // Calling power of 'i' raised to 'n' int p = power(curr_num, n); while (p + curr_sum < x) { // Recursively check all greater values of i results += checkRecursive(x, n, curr_num + 1, p + curr_sum); curr_num++; p = power(curr_num, n); } // If sum of powers is equal to x // then increase the value of result. if (p + curr_sum == x) results++; // Return the final result return results; } // Driver Code. public static void Main() { int x = 10, n = 2; System.Console.WriteLine( checkRecursive(x, n, 1, 0)); } } // This code is contributed by mits
PHP
<?php // PHP program to count // number of ways any // given integer x can // be expressed as n-th // power of unique // natural numbers. // Function to calculate and return // the power of any given number function power($num, $n) { if ($n == 0) return 1; else if ($n % 2 == 0) return power($num, (int)($n / 2)) * power($num, (int)($n / 2)); else return $num * power($num, (int)($n / 2)) * power($num, (int)($n / 2)); } // Function to check power // representations recursively function checkRecursive($x, $n, $curr_num = 1, $curr_sum = 0) { // Initialize number of // ways to express // x as n-th powers // of different natural // numbers $results = 0; // Calling power of 'i' // raised to 'n' $p = power($curr_num, $n); while ($p + $curr_sum < $x) { // Recursively check all // greater values of i $results += checkRecursive($x, $n, $curr_num + 1, $p + $curr_sum); $curr_num++; $p = power($curr_num, $n); } // If sum of powers // is equal to x // then increase the // value of result. if ($p + $curr_sum == $x) $results++; // Return the final result return $results; } // Driver Code. $x = 10; $n = 2; echo(checkRecursive($x, $n)); // This code is contributed by Ajit. ?>
Javascript
<script> // javascript program to count number of ways any // given integer x can be expressed as n-th // power of unique natural numbers. // Function to calculate and return the // power of any given number function power(num , n) { if (n == 0) return 1; else if (n % 2 == 0) return power(num, parseInt(n / 2)) * power(num, parseInt(n / 2)); else return num * power(num,parseInt(n / 2)) * power(num, parseInt(n / 2)); } // Function to check power representations recursively function checkRecursive(x , n , curr_num , curr_sum) { // Initialize number of ways to express // x as n-th powers of different natural // numbers var results = 0; // Calling power of 'i' raised to 'n' var p = power(curr_num, n); while (p + curr_sum < x) { // Recursively check all greater values of i results += checkRecursive(x, n, curr_num + 1, p + curr_sum); curr_num++; p = power(curr_num, n); } // If sum of powers is equal to x // then increase the value of result. if (p + curr_sum == x) results++; // Return the final result return results; } // Driver Code. var x = 10, n = 2; document.write(checkRecursive(x, n, 1, 0)); // This code is contributed by gauravrajput1 </script>
1
Solución alternativa:
A continuación se muestra una solución alternativa más sencilla proporcionada por Shivam Kanodia .
C++
// C++ program to find number of ways to express // a number as sum of n-th powers of numbers. #include<bits/stdc++.h> using namespace std; int res = 0; int checkRecursive(int num, int x, int k, int n) { if (x == 0) res++; int r = (int)floor(pow(num, 1.0 / n)); for (int i = k + 1; i <= r; i++) { int a = x - (int)pow(i, n); if (a >= 0) checkRecursive(num, x - (int)pow(i, n), i, n); } return res; } // Wrapper over checkRecursive() int check(int x, int n) { return checkRecursive(x, x, 0, n); } // Driver Code int main() { cout << (check(10, 2)); return 0; } // This code is contributed by mits
C
// C program to find number of ways to express // a number as sum of n-th powers of numbers. #include <math.h> #include <stdio.h> int res = 0; int checkRecursive(int num, int x, int k, int n) { if (x == 0) res++; int r = (int)floor(pow(num, 1.0 / n)); for (int i = k + 1; i <= r; i++) { int a = x - (int)pow(i, n); if (a >= 0) checkRecursive(num, x - (int)pow(i, n), i, n); } return res; } // Wrapper over checkRecursive() int check(int x, int n) { return checkRecursive(x, x, 0, n); } // Driver Code int main() { printf("%d", (check(10, 2))); return 0; } // This code is contributed by Rohit Pradhan
Java
// Java program to find number of ways to express a // number as sum of n-th powers of numbers. import java.io.*; import java.util.*; public class Solution { static int res = 0; static int checkRecursive(int num, int x, int k, int n) { if (x == 0) res++; int r = (int)Math.floor(Math.pow(num, 1.0 / n)); for (int i = k + 1; i <= r; i++) { int a = x - (int)Math.pow(i, n); if (a >= 0) checkRecursive(num, x - (int)Math.pow(i, n), i, n); } return res; } // Wrapper over checkRecursive() static int check(int x, int n) { return checkRecursive(x, x, 0, n); } public static void main(String[] args) { System.out.println(check(10, 2)); } }
Python3
# Python 3 program to find number of ways to express # a number as sum of n-th powers of numbers. def checkRecursive(num, rem_num, next_int, n, ans=0): if (rem_num == 0): ans += 1 r = int(num**(1 / n)) for i in range(next_int + 1, r + 1): a = rem_num - int(i**n) if a >= 0: ans += checkRecursive(num, rem_num - int(i**n), i, n, 0) return ans # Wrapper over checkRecursive() def check(x, n): return checkRecursive(x, x, 0, n) # Driver Code if __name__ == '__main__': print(check(10, 2)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find number of // ways to express a number as sum // of n-th powers of numbers. using System; class Solution { static int res = 0; static int checkRecursive(int num, int x, int k, int n) { if (x == 0) res++; int r = (int)Math.Floor(Math.Pow(num, 1.0 / n)); for (int i = k + 1; i <= r; i++) { int a = x - (int)Math.Pow(i, n); if (a >= 0) checkRecursive(num, x - (int)Math.Pow(i, n), i, n); } return res; } // Wrapper over checkRecursive() static int check(int x, int n) { return checkRecursive(x, x, 0, n); } // Driver code public static void Main() { Console.WriteLine(check(10, 2)); } } // This code is contributed by vt_m.
PHP
<?php // PHP program to find number // of ways to express a number // as sum of n-th powers of numbers. $res = 0; function checkRecursive($num, $x, $k, $n) { global $res; if ($x == 0) $res++; $r = (int)floor(pow($num, 1.0 / $n)); for ($i = $k + 1; $i <= $r; $i++) { $a = $x - (int)pow($i, $n); if ($a >= 0) checkRecursive($num, $x - (int)pow($i, $n), $i, $n); } return $res; } // Wrapper over // checkRecursive() function check($x, $n) { return checkRecursive($x, $x, 0, $n); } // Driver Code echo (check(10, 2)); // This code is contributed by ajit ?>
Javascript
<script> // JavaScript program for the above approach let res = 0; function checkRecursive(num, x, k, n) { if (x == 0) res++; let r = Math.floor(Math.pow(num, 1.0 / n)); for (let i = k + 1; i <= r; i++) { let a = x - Math.pow(i, n); if (a >= 0) checkRecursive(num, x - Math.pow(i, n), i, n); } return res; } // Wrapper over checkRecursive() function check(x, n) { return checkRecursive(x, x, 0, n); } // Driver Code document.write(check(10, 2)); // This code is contributed by splevel62. </script>
1
Solución recursiva simple:
aportado por Ram Jondhale .
C++
#include <iostream> #include<cmath> using namespace std; //Helper function int getAllWaysHelper(int remainingSum, int power, int base){ //calculate power int result = pow(base, power); if(remainingSum == result) return 1; if(remainingSum < result) return 0; //Two recursive calls one to include current base's power in sum another to exclude int x = getAllWaysHelper(remainingSum - result, power, base + 1); int y = getAllWaysHelper(remainingSum, power, base+1); return x + y; } int getAllWays(int sum, int power) { return getAllWaysHelper(sum, power, 1); } // Driver Code. int main() { int x = 10, n = 2; cout << getAllWays(x, n); return 0; }
Java
// Java program to implement the approach import java.io.*; class GFG { public static int getAllWaysHelper(int remainingSum, int power, int base) { // calculate power int result = (int)Math.pow(base, power); if (remainingSum == result) return 1; if (remainingSum < result) return 0; // Two recursive calls one to include current base's // power in sum another to exclude int x = getAllWaysHelper(remainingSum - result, power, base + 1); int y = getAllWaysHelper(remainingSum, power, base + 1); return x + y; } public static int getAllWays(int sum, int power) { return getAllWaysHelper(sum, power, 1); } // Driver Code public static void main(String[] args) { int x = 10, n = 2; System.out.print(getAllWays(x, n)); } } // This code is contributed by Rohit Pradhan
Python3
# Helper function def getAllWaysHelper(remainingSum, power, base): # calculate power result = pow(base, power) if(remainingSum == result): return 1 if(remainingSum < result): return 0 # Two recursive calls one to include # current base's power in sum another to exclude x = getAllWaysHelper(remainingSum - result, power, base + 1) y = getAllWaysHelper(remainingSum, power, base+1) return x + y def getAllWays(sum, power): return getAllWaysHelper(sum, power, 1) # Driver Code x,n = 10,2 print(getAllWays(x, n)) # This code is contributed by shinjanpatra.
C#
using System; class GFG { // Helper function static int getAllWaysHelper(int remainingSum, int power, int bases) { // calculate power int result = (int)Math.Pow(bases, power); if (remainingSum == result) return 1; if (remainingSum < result) return 0; // Two recursive calls one to include current base's // power in sum another to exclude int x = getAllWaysHelper(remainingSum - result, power, bases + 1); int y = getAllWaysHelper(remainingSum, power, bases + 1); return x + y; } static int getAllWays(int sum, int power) { return getAllWaysHelper(sum, power, 1); } // Driver Code. public static int Main() { int x = 10, n = 2; Console.Write(getAllWays(x, n)); return 0; } } // This code is contributed by Taranpreet
Javascript
<script> // Helper function function getAllWaysHelper(remainingSum, power, base) { // calculate power let result = Math.pow(base, power); if(remainingSum == result) return 1; if(remainingSum < result) return 0; // Two recursive calls one to include // current base's power in sum another to exclude let x = getAllWaysHelper(remainingSum - result, power, base + 1); let y = getAllWaysHelper(remainingSum, power, base+1); return x + y; } function getAllWays(sum, power) { return getAllWaysHelper(sum, power, 1); } // Driver Code. let x = 10, n = 2; document.write(getAllWays(x, n)); // This code is contributed by shinjanpatra </script>
1
Este artículo es una contribución de DANISH KALEEM . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA