Dado un número entero N , la tarea es encontrar el número de formas de representar el número N como suma de cuadrados perfectos .
Ejemplos:
Entrada: N = 9
Salida: 4
Explicación:
Hay cuatro maneras de representar 9 como la suma de cuadrados perfectos:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9
1 + 1 + 1 + 1 + 1 + 4 = 9
1 + 4 + 4 = 9
9 = 9Entrada: N =8
Salida: 3
Enfoque ingenuo: la idea es almacenar todos los cuadrados perfectos menores o iguales a N en una array . El problema ahora se reduce a encontrar las formas de sumar a N usando elementos de array con repetición permitida , lo que puede resolverse usando recursividad . Siga los pasos a continuación para resolver el problema:
- Almacene todos los cuadrados perfectos menores o iguales a N y en una array psquare[] .
- Cree una función recursiva countWays(index, target) que tome dos parámetros index , (inicialmente N-1) y target (inicialmente N):
- Manejar los casos base:
- Si el destino es 0, devuelve 1.
- Si el índice o el destino es menor que 0, devuelve 0.
- De lo contrario, incluya el elemento psquare[index] en la suma restándolo del objetivo y llamando recursivamente al valor restante de target .
- Excluya el elemento, psquare[index] de la suma moviéndose al siguiente índice y llamando recursivamente al mismo valor de target .
- Devuelve la suma obtenida al incluir y excluir el elemento.
- Manejar los casos base:
- Imprime el valor de countWays(N-1, N) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Store perfect squares
// less than or equal to N
vector<int> psquare;
// Utility function to calculate perfect
// squares less than or equal to N
void calcPsquare(int N)
{
for (int i = 1; i * i <= N; i++)
psquare.push_back(i * i);
}
// Function to find the number
// of ways to represent a number
// as sum of perfect squares
int countWays(int index, int target)
{
// Handle the base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// Include the i-th index element
int inc = countWays(
index, target - psquare[index]);
// Exclude the i-th index element
int exc = countWays(index - 1, target);
// Return the result
return inc + exc;
}
// Driver Code
int main()
{
// Given Input
int N = 9;
// Precalculate perfect
// squares <= N
calcPsquare(N);
// Function Call
cout << countWays(psquare.size() - 1, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Store perfect squares
// less than or equal to N
static ArrayList<Integer> psquare = new ArrayList<>();
// Utility function to calculate perfect
// squares less than or equal to N
static void calcPsquare(int N)
{
for (int i = 1; i * i <= N; i++)
psquare.add(i * i);
}
// Function to find the number
// of ways to represent a number
// as sum of perfect squares
static int countWays(int index, int target)
{
// Handle the base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// Include the i-th index element
int inc
= countWays(index, target - psquare.get(index));
// Exclude the i-th index element
int exc = countWays(index - 1, target);
// Return the result
return inc + exc;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int N = 9;
// Precalculate perfect
// squares <= N
calcPsquare(N);
// Function Call
System.out.print(countWays(psquare.size() - 1, N));
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Store perfect squares # less than or equal to N psquare = [] # Utility function to calculate perfect # squares less than or equal to N def calcPsquare(N): for i in range(1, N): if i * i > N: break psquare.append(i * i) # Function to find the number # of ways to represent a number # as sum of perfect squares def countWays(index, target): # Handle the base cases if (target == 0): return 1 if (index < 0 or target < 0): return 0 # Include the i-th index element inc = countWays(index, target - psquare[index]) # Exclude the i-th index element exc = countWays(index - 1, target) # Return the result return inc + exc # Driver Code if __name__ == '__main__': # Given Input N = 9 # Precalculate perfect # squares <= N calcPsquare(N) # Function Call print (countWays(len(psquare) - 1, N)) # This code is contributed by mohit kumar 29
C#
using System.IO;
using System;
using System.Collections;
class GFG {
// Store perfect squares
// less than or equal to N
static ArrayList psquare = new ArrayList();
// Utility function to calculate perfect
// squares less than or equal to N
static void calcPsquare(int N)
{
for (int i = 1; i * i <= N; i++)
psquare.Add(i * i);
}
// Function to find the number
// of ways to represent a number
// as sum of perfect squares
static int countWays(int index, int target)
{
// Handle the base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// Include the i-th index element
int inc = countWays(index,
target - (int)psquare[index]);
// Exclude the i-th index element
int exc = countWays(index - 1, target);
// Return the result
return inc + exc;
}
static void Main()
{
// Given Input
int N = 9;
// Precalculate perfect
// squares <= N
calcPsquare(N);
// Function Call
Console.WriteLine(countWays(psquare.Count - 1, N));
}
}
// This code is contributed by abhinavjain194.
Javascript
<script>
// JavaScript program for the above approach
// Store perfect squares
// less than or equal to N
var psquare = []
// Utility function to calculate perfect
// squares less than or equal to N
function calcPsquare(N)
{
var i;
for (i = 1; i * i <= N; i++)
psquare.push(i * i);
}
// Function to find the number
// of ways to represent a number
// as sum of perfect squares
function countWays(index, target)
{
// Handle the base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// Include the i-th index element
var inc = countWays(
index, target - psquare[index]);
// Exclude the i-th index element
var exc = countWays(index - 1, target);
// Return the result
return inc + exc;
}
// Driver Code
// Given Input
var N = 9;
// Precalculate perfect
// squares <= N
calcPsquare(N);
// Function Call
document.write(countWays(psquare.length - 1, N));
</script>
Producción:
4
Complejidad Temporal: O(2 K ), donde K es el número de cuadrados perfectos menores o iguales a N
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema tiene subproblemas superpuestos y una propiedad de subestructura óptima . Para optimizar el enfoque anterior, la idea es usar programación dinámica al memorizar las llamadas recursivas anteriores usando una array 2D de tamaño K*N , donde K es el número de cuadrados perfectos menores o iguales que N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Store perfect squares
// less than or equal to N
vector<int> psquare;
// Utility function to calculate
// perfect squares <= N
void calcPsquare(int N)
{
for (int i = 1; i * i <= N; i++)
psquare.push_back(i * i);
}
// DP array for memoization
vector<vector<int> > dp;
// Recursive function to count
// number of ways to represent
// a number as a sum of perfect squares
int countWaysUtil(int index, int target)
{
// Handle base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// If already computed, return the result
if (dp[index][target] != -1)
return dp[index][target];
// Else, compute the result
return dp[index][target]
= countWaysUtil(
index, target - psquare[index])
+ countWaysUtil(
index - 1, target);
}
// Function to find the number of ways to
// represent a number as a sum of perfect squares
int countWays(int N)
{
// Precalculate perfect squares less
// than or equal to N
calcPsquare(N);
// Create dp array to memoize
dp.resize(psquare.size() + 1,
vector<int>(N + 1, -1));
// Function call to fill dp array
return countWaysUtil(psquare.size() - 1, N);
}
// Driver Code
int main()
{
// Given Input
int N = 9;
// Function Call
cout << countWays(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Store perfect squares
// less than or equal to N
private static ArrayList<Integer> psquare;
// Utility function to calculate
// perfect squares <= N
private static void calcPsquare(int n) {
for (int i = 1; i * i <= n; i++)
psquare.add(i * i);
}
// DP array for memoization
private static int[][] dp;
// Recursive function to count
// number of ways to represent
// a number as a sum of perfect squares
private static int countWaysUtil(int index, int target) {
// Handle base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// If already computed, return the result
if (dp[index][target] != -1)
return dp[index][target];
// Else, compute the result
return dp[index][target]
= countWaysUtil(
index, target - psquare.get(index))
+ countWaysUtil(
index - 1, target);
}
// Function to find the number of ways to
// represent a number as a sum of perfect squares
private static int countWays(int n) {
// Precalculate perfect squares less
// than or equal to N
psquare = new ArrayList<Integer>();
calcPsquare(n);
// Create dp array to memoize
dp = new int[psquare.size()+1][n+1];
for(int i = 0; i<=psquare.size(); i++)Arrays.fill(dp[i], -1);
// Function call to fill dp array
return countWaysUtil(psquare.size() - 1, n);
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int N = 9;
// Function Call
System.out.print(countWays(N));
}
}
// This code is contributed by Dheeraj Bhagchandani.
Python3
# Python3 program for the above approach from math import sqrt # Store perfect squares # less than or equal to N psquare = [] # DP array for memoization dp = [] # Utility function to calculate # perfect squares <= N def calcPsquare(N): global psquare for i in range(1, int(sqrt(N)) + 1, 1): psquare.append(i * i) # Recursive function to count # number of ways to represent # a number as a sum of perfect squares def countWaysUtil(index, target): global dp # Handle base cases if (target == 0): return 1 if (index < 0 or target < 0): return 0 # If already computed, return the result if (dp[index][target] != -1): return dp[index][target] dp[index][target] = (countWaysUtil( index, target - psquare[index]) + countWaysUtil(index - 1, target)) # Else, compute the result return dp[index][target] # Function to find the number of ways to # represent a number as a sum of perfect squares def countWays(N): global dp global psquare # Precalculate perfect squares less # than or equal to N calcPsquare(N) temp = [-1 for i in range(N + 1)] # Create dp array to memoize dp = [temp for i in range(len(psquare) + 1)] # Function call to fill dp array return countWaysUtil(len(psquare) - 1, N) - 1 # Driver Code if __name__ == '__main__': # Given Input N = 9 # Function Call print(countWays(N)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Store perfect squares
// less than or equal to N
static List<int> psquare;
// Utility function to calculate
// perfect squares <= N
private static void calcPsquare(int n)
{
for(int i = 1; i * i <= n; i++)
psquare.Add(i * i);
}
// DP array for memoization
private static int[,]dp;
// Recursive function to count
// number of ways to represent
// a number as a sum of perfect squares
private static int countWaysUtil(int index,
int target)
{
// Handle base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// If already computed, return the result
if (dp[index, target] != -1)
return dp[index, target];
// Else, compute the result
return dp[index, target] = countWaysUtil(index,
target - psquare[index]) +
countWaysUtil(index - 1, target);
}
// Function to find the number of ways to
// represent a number as a sum of perfect squares
private static int countWays(int n)
{
// Precalculate perfect squares less
// than or equal to N
psquare = new List<int>();
calcPsquare(n);
// Create dp array to memoize
dp = new int[psquare.Count + 1, n + 1];
for(int i = 0; i <= psquare.Count; i++)
{
for(int j = 0; j <= n; j++)
{
dp[i, j] = -1;
}
//Array.Fill(dp[i], -1);
}
// Function call to fill dp array
return countWaysUtil(psquare.Count - 1, n);
}
// Driver Code
static void Main()
{
// Given Input
int N = 9;
// Function Call
Console.Write(countWays(N));
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// JavaScript program for the above approach
let psquare;
function calcPsquare(n)
{
for (let i = 1; i * i <= n; i++)
psquare.push(i * i);
}
// DP array for memoization
let dp;
// Recursive function to count
// number of ways to represent
// a number as a sum of perfect squares
function countWaysUtil(index,target)
{
// Handle base cases
if (target == 0)
return 1;
if (index < 0 || target < 0)
return 0;
// If already computed, return the result
if (dp[index][target] != -1)
return dp[index][target];
// Else, compute the result
return dp[index][target]
= countWaysUtil(
index, target - psquare[index])
+ countWaysUtil(
index - 1, target);
}
// Function to find the number of ways to
// represent a number as a sum of perfect squares
function countWays(n)
{
// Precalculate perfect squares less
// than or equal to N
psquare = [];
calcPsquare(n);
// Create dp array to memoize
dp = new Array(psquare.length+1);
for(let i=0;i<psquare.length+1;i++)
{
dp[i]=new Array(n+1);
for(let j=0;j<n+1;j++)
{
dp[i][j]=-1;
}
}
// Function call to fill dp array
return countWaysUtil(psquare.length - 1, n);
}
// Driver Code
// Given Input
let N = 9;
// Function Call
document.write(countWays(N));
// This code is contributed by patel2127
</script>
Producción
4
Complejidad Temporal: O(K*N), donde K es el número de cuadrados perfectos menores o iguales a N
Espacio Auxiliar: O(K*N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA