Count ways to represent a number as sum of perfect squares

0 0 10 minutes read

Given an integer N, the task is to find the number of ways to represent the number N as sum of perfect squares.

Examples:

Input: N = 9
Output: 4
Explanation:
There are four ways to represent 9 as the sum of perfect squares:
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9
1 + 1 + 1 + 1 + 1 + 4 = 9
1 + 4 + 4 = 9
9 = 9

Input: N = 8
Output: 3

Naive Approach: The idea is to store all the perfect squares less than or equal to N in an array. The problem now reduces to finding the ways to sum to N using array elements with repetition allowed which can be solved using recursion. Follow the steps below to solve the problem:

Store all the perfect squares less than or equal to N and in an array psquare[].
Create a recursion function countWays(index, target) that takes two parameters index, (initially N-1) and target (initially N):
- Handle the base cases:
  - If the target is 0, return 1.
  - If either index or target is less than 0, return 0.
- Otherwise, include the element, psquare[index] in the sum by subtracting it from the target and recursively calling for the remaining value of target.
- Exclude the element, psquare[index] from the sum by moving to the next index and recursively calling for the same value of target.
- Return the sum obtained by including and excluding the element.
Print the value of countWays(N-1, N) as the result.

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(2^K), where K is the number of perfect squares less than or equal to N
Auxiliary Space: O(1)

Efficient approach: This problem has overlapping subproblems and optimal substructure property. To optimize the above approach, the idea is to use dynamic programming by memoizing the above recursive calls using a 2D array of size K*N, where K is the number of perfect squares less than or equal to N.

Below is the implementation of the above approach:

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>

Output

Time Complexity: O(K*N), where K is the number of perfect squares less than or equal to N
Auxiliary Space: O(K*N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!