Posted on by Kalkicode
Code Backtracking

Find all perfect square root of n digit

In this article, we will explore a C program that finds all the perfect square roots of an n-digit number. The program calculates the sum of squares of digits and checks if it is a perfect square. If it is, the program displays the combination of digits and the corresponding square root of the sum.

Problem Statement

The problem is to find all the perfect square roots of an n-digit number. We need to calculate the sum of squares of n-digit numbers and check if the sum is a perfect square. If it is, we display the combination of digits and the corresponding square root of the sum.

Example

Let's take an example to understand the problem better. Suppose we want to find all the perfect square roots of 3-digit numbers. The program will generate the following output:

Perfect Square of 3 digits are
1²+2²+2² = 9(3²)
1²+4²+8² = 81(9²)
2²+3²+6² = 49(7²)
2²+4²+4² = 36(6²)
2²+6²+9² = 121(11²)
3²+6²+6² = 81(9²)
4²+4²+7² = 81(9²)
4²+8²+8² = 144(12²)
6²+6²+7² = 121(11²)

Algorithm and Pseudocode

1. Define a function isSquareRoot(sum) that takes an integer sum as input and checks if it is a perfect square.

function isSquareRoot(sum):
	value = sqrt(sum)
	if value * value == sum:
		return 1
	return 0

2. Define a function show(output, n, sum) that displays the calculated result.

function show(output, n, sum):
	for i = 0 to n-1:
		if i != 0:
			print "+"
		print output[i] + "²"
	print " = " + sum + "(" + sqrt(sum) + "²)"

3. Define a recursive function perfectSquare(output, n, counter, num, sum) that finds all the perfect square roots of n-digit numbers.

function perfectSquare(output, n, counter, num, sum):
	if counter == n:
		if isSquareRoot(sum):
			show(output, n, sum)
		return
	for x = num to 9:
		output[counter] = x
		sum += x * x
		perfectSquare(output, n, counter + 1, x, sum)
		sum -= x * x

4. Define a function findDigitSquare(digit) that handles the request of finding the digit square sum.

function findDigitSquare(digit):
	if digit <= 0:
		return
	output[digit]
	print "\nPerfect Square of " + digit + " digits are\n"
	perfectSquare(output, digit, 0, 1, 0)

5. In the main() function, test the program for different cases.

function main():
	findDigitSquare(3)
	findDigitSquare(4)

Code Solution

// C program 
// Find all perfect square root of n digit
#include <stdio.h>
#include <math.h>
int isSquareRoot(int sum)
{
	int value = (int) sqrt(sum);
	if (value *value == sum)
	{
		return 1;
	}
	return 0;
}
// Display Calculated result 
void show(int output[], int n, int sum)
{
	for (int i = 0; i < n; ++i)
	{
		if (i != 0)
		{
			printf("+");
		}
		printf("%d²", output[i]);
	}
	printf(" = %d(%d²)\n ", sum, (int) sqrt(sum));
}
// Find all perfect square root of n digit sum
void perfectSquare(int output[], int n, int counter, int num, int sum)
{
	if (counter == n)
	{
		if (isSquareRoot(sum))
		{
			show(output, n, sum);
		}
		return;
	}
	for (int x = num; x <= 9; ++x)
	{
		output[counter] = x;
		sum += x *x;
		perfectSquare(output, n, counter + 1, x, sum);
		sum -= x *x;
	}
}
// Handles the request of finding digit square sum
void findDigitSquare(int digit)
{
	if (digit <= 0)
	{
		// When digit is less than 1
		return;
	}
	// Assume digit is not exceed the length of maximum numbers
	int output[digit];
	printf("\n Perfect Square of %d digits are \n ", digit);
	perfectSquare(output, digit, 0, 1, 0);
}
int main()
{
	// Test case
	findDigitSquare(3);
	findDigitSquare(4);
	return 0;
}

Output

 Perfect Square of 3 digits are
 1²+2²+2² = 9(3²)
 1²+4²+8² = 81(9²)
 2²+3²+6² = 49(7²)
 2²+4²+4² = 36(6²)
 2²+6²+9² = 121(11²)
 3²+6²+6² = 81(9²)
 4²+4²+7² = 81(9²)
 4²+8²+8² = 144(12²)
 6²+6²+7² = 121(11²)

 Perfect Square of 4 digits are
 1²+1²+1²+1² = 4(2²)
 1²+1²+3²+5² = 36(6²)
 1²+1²+7²+7² = 100(10²)
 1²+2²+2²+4² = 25(5²)
 1²+3²+3²+9² = 100(10²)
 1²+4²+4²+4² = 49(7²)
 1²+5²+5²+7² = 100(10²)
 2²+2²+2²+2² = 16(4²)
 2²+2²+3²+8² = 81(9²)
 2²+2²+4²+5² = 49(7²)
 2²+2²+7²+8² = 121(11²)
 2²+4²+4²+8² = 100(10²)
 2²+4²+5²+6² = 81(9²)
 2²+8²+8²+8² = 196(14²)
 3²+3²+3²+3² = 36(6²)
 3²+5²+9²+9² = 196(14²)
 4²+4²+4²+4² = 64(8²)
 4²+4²+5²+8² = 121(11²)
 4²+5²+8²+8² = 169(13²)
 4²+6²+6²+9² = 169(13²)
 4²+8²+8²+9² = 225(15²)
 5²+5²+5²+5² = 100(10²)
 6²+6²+6²+6² = 144(12²)
 7²+7²+7²+7² = 196(14²)
 8²+8²+8²+8² = 256(16²)
 9²+9²+9²+9² = 324(18²)
/*
  Java Program for
  Find all perfect square root of n digit number
*/

public class DigitSquare
{
   
    public boolean isSquareRoot(int sum)
    {
        int value = (int) Math.sqrt(sum);
        if (value * value == sum)
        {
            return true;
        }
        return false;
    }
    // Display Calculated result 
    public void show(int[] output, int n, int sum)
    {
        for (int i = 0; i < n; ++i)
        {
            if (i != 0)
            {
                System.out.print("+");
            }
            System.out.print(" "+output[i] + "²");
        }
        System.out.print(" = " + sum + "(" + (int) Math.sqrt(sum) + "²)\n");
    }
    // Find all perfect square root of n digit sum
    public void perfectSquare(int[] output, int n, int counter, int num, int sum)
    {
        if (counter == n)
        {
            if (isSquareRoot(sum))
            {
                show(output, n, sum);
            }
            return;
        }
        for (int x = num; x <= 9; ++x)
        {
            output[counter] = x;
            sum += x * x;
            perfectSquare(output, n, counter + 1, x, sum);
            sum -= x * x;
        }
    }
    // Handles the request of finding digit square sum
    public void findDigitSquare(int digit)
    {
        if (digit <= 0)
        {
            // When digit is less than 1
            return;
        }
        // Assume digit is not exceed the length of maximum numbers
        int[] output = new int[digit];
        System.out.print("\n Perfect Square of " + digit + " digits are \n");
        perfectSquare(output, digit, 0, 1, 0);
    }
    public static void main(String[] args)
    {
        DigitSquare task = new DigitSquare();
        // Test case
        task.findDigitSquare(3);
        task.findDigitSquare(4);
    }
}

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
// Include header file
#include <iostream>
#include <math.h>
using namespace std;

/*
  C++ Program for
  Find all perfect square root of n digit number
*/

class DigitSquare
{
	public: bool isSquareRoot(int sum)
	{
		int value = (int) sqrt(sum);
		if (value *value == sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	void show(int output[], int n, int sum)
	{
		for (int i = 0; i < n; ++i)
		{
			if (i != 0)
			{
				cout << "+";
			}
			cout << " " << output[i] << "²";
		}
		cout << " = " << sum << "(" << (int) sqrt(sum) << "²)\n";
	}
	// Find all perfect square root of n digit sum
	void perfectSquare(int output[], int n, int counter, int num, int sum)
	{
		if (counter == n)
		{
			if (this->isSquareRoot(sum))
			{
				this->show(output, n, sum);
			}
			return;
		}
		for (int x = num; x <= 9; ++x)
		{
			output[counter] = x;
			sum += x *x;
			this->perfectSquare(output, n, counter + 1, x, sum);
			sum -= x *x;
		}
	}
	// Handles the request of finding digit square sum
	void findDigitSquare(int digit)
	{
		// When digit is less than 1
		if (digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		int output[digit];
		cout << "\n Perfect Square of " << digit << " digits are \n";
		this->perfectSquare(output, digit, 0, 1, 0);
	}
};
int main()
{
	DigitSquare task = DigitSquare();
	// Test case
	task.findDigitSquare(3);
	task.findDigitSquare(4);
	return 0;
}

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
// Include namespace system
using System;
/*
  C# Program for
  Find all perfect square root of n digit number
*/
public class DigitSquare
{
	public Boolean isSquareRoot(int sum)
	{
		int value = (int) Math.Sqrt(sum);
		if (value * value == sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	public void show(int[] output, int n, int sum)
	{
		for (int i = 0; i < n; ++i)
		{
			if (i != 0)
			{
				Console.Write("+");
			}
			Console.Write(" " + output[i] + "²");
		}
		Console.Write(" = " + sum + "(" + (int) Math.Sqrt(sum) + "²)\n");
	}
	// Find all perfect square root of n digit sum
	public void perfectSquare(int[] output, int n, int counter, int num, int sum)
	{
		if (counter == n)
		{
			if (isSquareRoot(sum))
			{
				show(output, n, sum);
			}
			return;
		}
		for (int x = num; x <= 9; ++x)
		{
			output[counter] = x;
			sum += x * x;
			perfectSquare(output, n, counter + 1, x, sum);
			sum -= x * x;
		}
	}
	// Handles the request of finding digit square sum
	public void findDigitSquare(int digit)
	{
		// When digit is less than 1
		if (digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		int[] output = new int[digit];
		Console.Write("\n Perfect Square of " + digit + " digits are \n");
		perfectSquare(output, digit, 0, 1, 0);
	}
	public static void Main(String[] args)
	{
		DigitSquare task = new DigitSquare();
		// Test case
		task.findDigitSquare(3);
		task.findDigitSquare(4);
	}
}

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
<?php
/*
  Php Program for
  Find all perfect square root of n digit number
*/
class DigitSquare
{
	public	function isSquareRoot($sum)
	{
		$value = (int) sqrt($sum);
		if ($value * $value == $sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	public	function show($output, $n, $sum)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			if ($i != 0)
			{
				echo "+";
			}
			echo " ". $output[$i] ."²";
		}
		echo " = ". $sum ."(". (int) sqrt($sum) ."²)\n";
	}
	// Find all perfect square root of n digit sum
	public	function perfectSquare($output, $n, $counter, $num, $sum)
	{
		if ($counter == $n)
		{
			if ($this->isSquareRoot($sum))
			{
				$this->show($output, $n, $sum);
			}
			return;
		}
		for ($x = $num; $x <= 9; ++$x)
		{
			$output[$counter] = $x;
			$sum += $x * $x;
			$this->perfectSquare($output, $n, $counter + 1, $x, $sum);
			$sum -= $x * $x;
		}
	}
	// Handles the request of finding digit square sum
	public	function findDigitSquare($digit)
	{
		// When digit is less than 1
		if ($digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		$output = array_fill(0, $digit, 0);
		echo "\n Perfect Square of ". $digit ." digits are \n";
		$this->perfectSquare($output, $digit, 0, 1, 0);
	}
}

function main()
{
	$task = new DigitSquare();
	// Test case
	$task->findDigitSquare(3);
	$task->findDigitSquare(4);
}
main();

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
/*
  Node Js Program for
  Find all perfect square root of n digit number
*/
class DigitSquare
{
	isSquareRoot(sum)
	{
		var value = parseInt(Math.sqrt(sum));
		if (value * value == sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	show(output, n, sum)
	{
		for (var i = 0; i < n; ++i)
		{
			if (i != 0)
			{
				process.stdout.write("+");
			}
			process.stdout.write(" " + output[i] + "²");
		}
		process.stdout.write(" = " + sum + "(" + parseInt(Math.sqrt(sum)) + "²)\n");
	}
	// Find all perfect square root of n digit sum
	perfectSquare(output, n, counter, num, sum)
	{
		if (counter == n)
		{
			if (this.isSquareRoot(sum))
			{
				this.show(output, n, sum);
			}
			return;
		}
		for (var x = num; x <= 9; ++x)
		{
			output[counter] = x;
			sum += x * x;
			this.perfectSquare(output, n, counter + 1, x, sum);
			sum -= x * x;
		}
	}
	// Handles the request of finding digit square sum
	findDigitSquare(digit)
	{
		// When digit is less than 1
		if (digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		var output = Array(digit).fill(0);
		process.stdout.write("\n Perfect Square of " + digit + " digits are \n");
		this.perfectSquare(output, digit, 0, 1, 0);
	}
}

function main()
{
	var task = new DigitSquare();
	// Test case
	task.findDigitSquare(3);
	task.findDigitSquare(4);
}
main();

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
import math
#   Python 3 Program for
#   Find all perfect square root of n digit number

class DigitSquare :
	def isSquareRoot(self, sum) :
		value = int(math.sqrt(sum))
		if (value * value == sum) :
			return True
		
		return False
	
	#  Display Calculated result
	def show(self, output, n, sum) :
		i = 0
		while (i < n) :
			if (i != 0) :
				print("+", end = "")
			
			print("{0}²".format(output[i]),end="")
			i += 1
		
		print(" = {0}({1})² ".format(sum,int(math.sqrt(sum))))
	
	#  Find all perfect square root of n digit sum
	def perfectSquare(self, output, n, counter, num, sum) :
		if (counter == n) :
			if (self.isSquareRoot(sum)) :
				self.show(output, n, sum)
			
			return
		
		x = num
		while (x <= 9) :
			output[counter] = x
			sum += x * x
			self.perfectSquare(output, n, counter + 1, x, sum)
			sum -= x * x
			x += 1
		
	
	#  Handles the request of finding digit square sum
	def findDigitSquare(self, digit) :
		#  When digit is less than 1
		if (digit <= 0) :
			return
		
		#  Assume digit is not exceed the length of maximum numbers
		output = [0] * (digit)
		print("\n Perfect Square of ", digit ," digits are ")
		self.perfectSquare(output, digit, 0, 1, 0)
	

def main() :
	task = DigitSquare()
	#  Test case
	task.findDigitSquare(3)
	task.findDigitSquare(4)

if __name__ == "__main__": main()

Output

 Perfect Square of  3  digits are
1²+2²+2² = 9(3)²
1²+4²+8² = 81(9)²
2²+3²+6² = 49(7)²
2²+4²+4² = 36(6)²
2²+6²+9² = 121(11)²
3²+6²+6² = 81(9)²
4²+4²+7² = 81(9)²
4²+8²+8² = 144(12)²
6²+6²+7² = 121(11)²

 Perfect Square of  4  digits are
1²+1²+1²+1² = 4(2)²
1²+1²+3²+5² = 36(6)²
1²+1²+7²+7² = 100(10)²
1²+2²+2²+4² = 25(5)²
1²+3²+3²+9² = 100(10)²
1²+4²+4²+4² = 49(7)²
1²+5²+5²+7² = 100(10)²
2²+2²+2²+2² = 16(4)²
2²+2²+3²+8² = 81(9)²
2²+2²+4²+5² = 49(7)²
2²+2²+7²+8² = 121(11)²
2²+4²+4²+8² = 100(10)²
2²+4²+5²+6² = 81(9)²
2²+8²+8²+8² = 196(14)²
3²+3²+3²+3² = 36(6)²
3²+5²+9²+9² = 196(14)²
4²+4²+4²+4² = 64(8)²
4²+4²+5²+8² = 121(11)²
4²+5²+8²+8² = 169(13)²
4²+6²+6²+9² = 169(13)²
4²+8²+8²+9² = 225(15)²
5²+5²+5²+5² = 100(10)²
6²+6²+6²+6² = 144(12)²
7²+7²+7²+7² = 196(14)²
8²+8²+8²+8² = 256(16)²
9²+9²+9²+9² = 324(18)²
#   Ruby Program for
#   Find all perfect square root of n digit number

class DigitSquare 
	def isSquareRoot(sum) 
		value = (Math.sqrt(sum)).to_i
		if (value * value == sum) 
			return true
		end

		return false
	end

	#  Display Calculated result
	def show(output, n, sum) 
		i = 0
		while (i < n) 
			if (i != 0) 
				print("+")
			end

			print(" ", output[i] ,"²")
			i += 1
		end

		print(" = ", sum ,"(", (Math.sqrt(sum)).to_i ,"²)\n")
	end

	#  Find all perfect square root of n digit sum
	def perfectSquare(output, n, counter, num, sum) 
		if (counter == n) 
			if (self.isSquareRoot(sum)) 
				self.show(output, n, sum)
			end

			return
		end

		x = num
		while (x <= 9) 
			output[counter] = x
			sum += x * x
			self.perfectSquare(output, n, counter + 1, x, sum)
			sum -= x * x
			x += 1
		end

	end

	#  Handles the request of finding digit square sum
	def findDigitSquare(digit) 
		#  When digit is less than 1
		if (digit <= 0) 
			return
		end

		#  Assume digit is not exceed the length of maximum numbers
		output = Array.new(digit) {0}
		print("\n Perfect Square of ", digit ," digits are \n")
		self.perfectSquare(output, digit, 0, 1, 0)
	end

end

def main() 
	task = DigitSquare.new()
	#  Test case
	task.findDigitSquare(3)
	task.findDigitSquare(4)
end

main()

Output

 Perfect Square of 3 digits are 
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are 
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
/*
  Scala Program for
  Find all perfect square root of n digit number
*/
class DigitSquare
{
	def isSquareRoot(sum: Int): Boolean = {
		var value: Int = (Math.sqrt(sum)).toInt;
		if (value * value == sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	def show(output: Array[Int], n: Int, sum: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			if (i != 0)
			{
				print("+");
			}
			print(" " + output(i) + "²");
			i += 1;
		}
		print(" = " + sum + "(" + (Math.sqrt(sum)).toInt + "²)\n");
	}
	// Find all perfect square root of n digit sum
	def perfectSquare(output: Array[Int], n: Int, counter: Int, num: Int, sum: Int): Unit = {
		if (counter == n)
		{
			if (this.isSquareRoot(sum))
			{
				this.show(output, n, sum);
			}
			return;
		}
		var x: Int = num;
		while (x <= 9)
		{
			output(counter) = x;
			this.perfectSquare(output, n, counter + 1, x, sum + x * x);
			x += 1;
		}
	}
	// Handles the request of finding digit square sum
	def findDigitSquare(digit: Int): Unit = {
		// When digit is less than 1
		if (digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		var output: Array[Int] = Array.fill[Int](digit)(0);
		print("\n Perfect Square of " + digit + " digits are \n");
		this.perfectSquare(output, digit, 0, 1, 0);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: DigitSquare = new DigitSquare();
		// Test case
		task.findDigitSquare(3);
		task.findDigitSquare(4);
	}
}

Output

 Perfect Square of 3 digits are
 1²+ 2²+ 2² = 9(3²)
 1²+ 4²+ 8² = 81(9²)
 2²+ 3²+ 6² = 49(7²)
 2²+ 4²+ 4² = 36(6²)
 2²+ 6²+ 9² = 121(11²)
 3²+ 6²+ 6² = 81(9²)
 4²+ 4²+ 7² = 81(9²)
 4²+ 8²+ 8² = 144(12²)
 6²+ 6²+ 7² = 121(11²)

 Perfect Square of 4 digits are
 1²+ 1²+ 1²+ 1² = 4(2²)
 1²+ 1²+ 3²+ 5² = 36(6²)
 1²+ 1²+ 7²+ 7² = 100(10²)
 1²+ 2²+ 2²+ 4² = 25(5²)
 1²+ 3²+ 3²+ 9² = 100(10²)
 1²+ 4²+ 4²+ 4² = 49(7²)
 1²+ 5²+ 5²+ 7² = 100(10²)
 2²+ 2²+ 2²+ 2² = 16(4²)
 2²+ 2²+ 3²+ 8² = 81(9²)
 2²+ 2²+ 4²+ 5² = 49(7²)
 2²+ 2²+ 7²+ 8² = 121(11²)
 2²+ 4²+ 4²+ 8² = 100(10²)
 2²+ 4²+ 5²+ 6² = 81(9²)
 2²+ 8²+ 8²+ 8² = 196(14²)
 3²+ 3²+ 3²+ 3² = 36(6²)
 3²+ 5²+ 9²+ 9² = 196(14²)
 4²+ 4²+ 4²+ 4² = 64(8²)
 4²+ 4²+ 5²+ 8² = 121(11²)
 4²+ 5²+ 8²+ 8² = 169(13²)
 4²+ 6²+ 6²+ 9² = 169(13²)
 4²+ 8²+ 8²+ 9² = 225(15²)
 5²+ 5²+ 5²+ 5² = 100(10²)
 6²+ 6²+ 6²+ 6² = 144(12²)
 7²+ 7²+ 7²+ 7² = 196(14²)
 8²+ 8²+ 8²+ 8² = 256(16²)
 9²+ 9²+ 9²+ 9² = 324(18²)
import Foundation
/*
  Swift 4 Program for
  Find all perfect square root of n digit number
*/
class DigitSquare
{
	func isSquareRoot(_ sum: Int)->Bool
	{
		let value: Int = Int(sqrt(Double(sum)));
	if (value * value == sum)
	{
		return true;
	}
	return false;
}
// Display Calculated result
func show(_ output: [Int], _ n: Int, _ sum: Int)
{
	var i: Int = 0;
	while (i < n)
	{
		if (i  != 0)
		{
			print(terminator: "+");
		}
		print("\(output[i])²",terminator: "");
		i += 1;
	}
	print(" = \(sum) (\(Int(sqrt(Double(sum)))))²");
}
// Find all perfect square root of n digit sum
func perfectSquare(_ output: inout[Int], _ n: Int, _ counter: Int, _ num: Int, _ sum: Int)
{
	if (counter == n)
	{
		if (self.isSquareRoot(sum))
		{
			self.show(output, n, sum);
		}
		return;
	}
	var x: Int = num;
	while (x <= 9)
	{
		output[counter] = x;
		self.perfectSquare(&output, n, counter + 1, x, sum + x * x);
		x += 1;
	}
}
// Handles the request of finding digit square sum
func findDigitSquare(_ digit: Int)
{
	// When digit is less than 1
	if (digit <= 0)
	{
		return;
	}
	// Assume digit is not exceed the length of maximum numbers
	var output: [Int] = Array(repeating: 0, count: digit);
	print("\n Perfect Square of ", digit ," digits are ");
	self.perfectSquare(&output, digit, 0, 1, 0);
}
}
func main()
{
	let task: DigitSquare = DigitSquare();
	// Test case
	task.findDigitSquare(3);
	task.findDigitSquare(4);
}
main();

Output

 Perfect Square of  3  digits are
1²+2²+2² = 9 (3)²
1²+4²+8² = 81 (9)²
2²+3²+6² = 49 (7)²
2²+4²+4² = 36 (6)²
2²+6²+9² = 121 (11)²
3²+6²+6² = 81 (9)²
4²+4²+7² = 81 (9)²
4²+8²+8² = 144 (12)²
6²+6²+7² = 121 (11)²

 Perfect Square of  4  digits are
1²+1²+1²+1² = 4 (2)²
1²+1²+3²+5² = 36 (6)²
1²+1²+7²+7² = 100 (10)²
1²+2²+2²+4² = 25 (5)²
1²+3²+3²+9² = 100 (10)²
1²+4²+4²+4² = 49 (7)²
1²+5²+5²+7² = 100 (10)²
2²+2²+2²+2² = 16 (4)²
2²+2²+3²+8² = 81 (9)²
2²+2²+4²+5² = 49 (7)²
2²+2²+7²+8² = 121 (11)²
2²+4²+4²+8² = 100 (10)²
2²+4²+5²+6² = 81 (9)²
2²+8²+8²+8² = 196 (14)²
3²+3²+3²+3² = 36 (6)²
3²+5²+9²+9² = 196 (14)²
4²+4²+4²+4² = 64 (8)²
4²+4²+5²+8² = 121 (11)²
4²+5²+8²+8² = 169 (13)²
4²+6²+6²+9² = 169 (13)²
4²+8²+8²+9² = 225 (15)²
5²+5²+5²+5² = 100 (10)²
6²+6²+6²+6² = 144 (12)²
7²+7²+7²+7² = 196 (14)²
8²+8²+8²+8² = 256 (16)²
9²+9²+9²+9² = 324 (18)²
/*
  Kotlin Program for
  Find all perfect square root of n digit number
*/
class DigitSquare
{
	fun isSquareRoot(sum: Int): Boolean
	{
		var value: Int = Math.sqrt(sum.toDouble()).toInt();
		if (value * value == sum)
		{
			return true;
		}
		return false;
	}
	// Display Calculated result
	fun show(output: Array <Int> , n: Int, sum: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			if (i != 0)
			{
				print("+");
			}
			print("" + output[i] + "²");
			i += 1;
		}
		print(" = " + sum + "(" + Math.sqrt(sum.toDouble()).toInt() + "²)\n ");
	}
	// Find all perfect square root of n digit sum
	fun perfectSquare(output: Array < Int > , n: Int, counter: Int, num: Int, sum: Int): Unit
	{
		if (counter == n)
		{
			if (this.isSquareRoot(sum))
			{
				this.show(output, n, sum);
			}
			return;
		}
		var x: Int = num;
		while (x <= 9)
		{
			output[counter] = x;
			this.perfectSquare(output, n, counter + 1, x, sum + x * x);
			x += 1;
		}
	}
	// Handles the request of finding digit square sum
	fun findDigitSquare(digit: Int): Unit
	{
		// When digit is less than 1
		if (digit <= 0)
		{
			return;
		}
		// Assume digit is not exceed the length of maximum numbers
		var output: Array < Int > = Array(digit)
		{
			0
		};
		print("\n Perfect Square of " + digit + " digits are \n ");
		this.perfectSquare(output, digit, 0, 1, 0);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: DigitSquare = DigitSquare();
	// Test case
	task.findDigitSquare(3);
	task.findDigitSquare(4);
}

Output

 Perfect Square of 3 digits are
 1²+2²+2² = 9(3²)
 1²+4²+8² = 81(9²)
 2²+3²+6² = 49(7²)
 2²+4²+4² = 36(6²)
 2²+6²+9² = 121(11²)
 3²+6²+6² = 81(9²)
 4²+4²+7² = 81(9²)
 4²+8²+8² = 144(12²)
 6²+6²+7² = 121(11²)

 Perfect Square of 4 digits are
 1²+1²+1²+1² = 4(2²)
 1²+1²+3²+5² = 36(6²)
 1²+1²+7²+7² = 100(10²)
 1²+2²+2²+4² = 25(5²)
 1²+3²+3²+9² = 100(10²)
 1²+4²+4²+4² = 49(7²)
 1²+5²+5²+7² = 100(10²)
 2²+2²+2²+2² = 16(4²)
 2²+2²+3²+8² = 81(9²)
 2²+2²+4²+5² = 49(7²)
 2²+2²+7²+8² = 121(11²)
 2²+4²+4²+8² = 100(10²)
 2²+4²+5²+6² = 81(9²)
 2²+8²+8²+8² = 196(14²)
 3²+3²+3²+3² = 36(6²)
 3²+5²+9²+9² = 196(14²)
 4²+4²+4²+4² = 64(8²)
 4²+4²+5²+8² = 121(11²)
 4²+5²+8²+8² = 169(13²)
 4²+6²+6²+9² = 169(13²)
 4²+8²+8²+9² = 225(15²)
 5²+5²+5²+5² = 100(10²)
 6²+6²+6²+6² = 144(12²)
 7²+7²+7²+7² = 196(14²)
 8²+8²+8²+8² = 256(16²)
 9²+9²+9²+9² = 324(18²)

Result and Output Explanation

p>The output displays all the perfect square roots of 3-digit and 4-digit numbers. Each line represents a combination of digits where each digit is squared, and the sum of squares is calculated. The program checks if the sum is a perfect square and displays the sum and its square root in parentheses.

Time Complexity of the Code

The time complexity of the code is influenced by the number of recursive calls made in the perfectSquare() function. The function explores all possible combinations of digits to calculate the sum of squares.

Let's assume the input digit is n. The number of recursive calls made will be 9^n since each digit can range from 1 to 9.

Therefore, the time complexity of the code can be approximated as O(9^n).

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment