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>
Producción
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>
Producción
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>
Producción
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