Encuentre formas de expresar un número entero como la suma de la n-ésima potencia de números naturales únicos

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 posibilidad

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *