# Find the Largest N digit perfect square number in Base B - GeeksforGeeks (2023)

Given two integers N and B, the task is to find the largest N digit numbers of Base B which is a perfect square.
Examples:

Input: N = 2, B = 10
Output: 81
Explanation:
81 is the largest 2-digit perfect square in base 10.
Input: N = 1, B = 8
Output: 4
Explanation:
4 is the largest 1 digit Octal number which is also a perfect square.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Brute Force Approach:

1) isPerfectSquare checks if a given number is a perfect square.
2) decimalToBase converts a decimal number to any base.
3) largestNDigitPerfectSquare finds the largest N digit perfect square in base B.

largestNDigitPerfectSquare function first calculates the largest N digit number in base B. It then iterates over all numbers starting from this largest number and checks whether each number is a perfect square in decimal. If a perfect square is found, it converts it to base B and returns it.

Implementation of the above approach:

## C++

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to check if a number is a perfect square`

`bool` `isPerfectSquare(``int` `n) {`

`int` `root = ``sqrt``(n);`

`return` `(root * root == n);`

`}`

`// Function to convert decimal to any base`

`int` `decimalToBase(``int` `n, ``int` `base) {`

`int` `num = 0, count = 0;`

`while` `(n != 0) {`

`int` `rem = n % base;`

`num += rem * ``pow``(10, count);`

`count++;`

`n /= base;`

`}`

`return` `num;`

`}`

`// Function to find the largest N digit perfect square in base B`

`int` `largestNDigitPerfectSquare(``int` `N, ``int` `B) {`

`// Largest N digit number in base B is (B^N)-1`

`int` `largestNum = ``pow``(B, N) - 1;`

`// Check perfect squares starting from the largest number`

`for` `(``int` `i = largestNum; i >= 0; i--) {`

`int` `decimalNum = 0, count = 0;`

`int` `num = i;`

`while` `(num != 0) {`

`int` `rem = num % 10;`

`decimalNum += rem * ``pow``(B, count);`

`count++;`

`num /= 10;`

`}`

`if` `(isPerfectSquare(decimalNum)) {`

`return` `decimalToBase(decimalNum, B);`

`}`

`}`

`// If no perfect square is found, return -1`

`return` `-1;`

`}`

`int` `main() {`

`int` `N = 2, B = 10;`

`int` `largestPerfectSquare = largestNDigitPerfectSquare(N, B);`

`cout << largestPerfectSquare << endl;`

`return` `0;`

`}`

## Java

`import` `java.util.*;`

`public` `class` `Main {`

`// Function to check if a number is a perfect square`

`static` `boolean` `isPerfectSquare(``int` `n) {`

`int` `root = (``int``)Math.sqrt(n);`

`return` `(root * root == n);`

`}`

`// Function to convert decimal to any base`

`static` `int` `decimalToBase(``int` `n, ``int` `base) {`

`int` `num = ``0``, count = ``0``;`

`while` `(n != ``0``) {`

`int` `rem = n % base;`

`num += rem * (``int``)Math.pow(``10``, count);`

`count++;`

`n /= base;`

`}`

(Video) Perfect Square String | GeeksforGeeks

`return` `num;`

`}`

`// Function to find the largest N digit perfect square in base B`

`static` `int` `largestNDigitPerfectSquare(``int` `N, ``int` `B) {`

`// Largest N digit number in base B is (B^N)-1`

`int` `largestNum = (``int``)Math.pow(B, N) - ``1``;`

`// Check perfect squares starting from the largest number`

`for` `(``int` `i = largestNum; i >= ``0``; i--) {`

`int` `decimalNum = ``0``, count = ``0``;`

`int` `num = i;`

`while` `(num != ``0``) {`

`int` `rem = num % ``10``;`

`decimalNum += rem * (``int``)Math.pow(B, count);`

`count++;`

`num /= ``10``;`

`}`

`if` `(isPerfectSquare(decimalNum)) {`

`return` `decimalToBase(decimalNum, B);`

`}`

`}`

`// If no perfect square is found, return -1`

`return` `-``1``;`

`}`

`public` `static` `void` `main(String[] args) {`

`int` `N = ``2``, B = ``10``;`

`int` `largestPerfectSquare = largestNDigitPerfectSquare(N, B);`

`System.out.println(largestPerfectSquare);`

`}`

`}`

`// This code is contributed by Prajwal Kandekar`

## Python3

`import` `math`

`# Function to check if a number is a perfect square`

`def` `is_perfect_square(n):`

`root ``=` `int``(math.sqrt(n))`

`return` `root ``*` `root ``=``=` `n`

`# Function to convert decimal to any base`

`def` `decimal_to_base(n, base):`

`num, count ``=` `0``, ``0`

`while` `n !``=` `0``:`

`rem ``=` `n ``%` `base`

`num ``+``=` `rem ``*` `(``10` `*``*` `count)`

`count ``+``=` `1`

`n ``/``/``=` `base`

`return` `num`

`# Function to find the largest N digit perfect square in base B`

`def` `largest_n_digit_perfect_square(N, B):`

`# Largest N digit number in base B is (B^N)-1`

`largest_num ``=` `B ``*``*` `N ``-` `1`

`# Check perfect squares starting from the largest number`

`for` `i ``in` `range``(largest_num, ``-``1``, ``-``1``):`

`decimal_num, count ``=` `0``, ``0`

`num ``=` `i`

`while` `num !``=` `0``:`

`rem ``=` `num ``%` `10`

`decimal_num ``+``=` `rem ``*` `(B ``*``*` `count)`

`count ``+``=` `1`

`num ``/``/``=` `10`

`if` `is_perfect_square(decimal_num):`

`return` `decimal_to_base(decimal_num, B)`

`# If no perfect square is found, return -1`

`return` `-``1`

`if` `__name__ ``=``=` `'__main__'``:`

`N, B ``=` `2``, ``10`

`largest_perfect_square ``=` `largest_n_digit_perfect_square(N, B)`

`print``(largest_perfect_square)`

## Javascript

`// Function to check if a number is a perfect square`

`function` `isPerfectSquare(n) {`

(Video) Job-A-Thon 19 - Contest Analysis | GeeksforGeeks Practice

`let root = Math.floor(Math.sqrt(n));`

`return` `root * root === n;`

`}`

`// Function to convert decimal to any base`

`function` `decimalToBase(n, base) {`

`let num = 0, count = 0;`

`while` `(n !== 0) {`

`let rem = n % base;`

`num += rem * Math.pow(10, count);`

`count++;`

`n = Math.floor(n / base);`

`}`

`return` `num;`

`}`

`// Function to find the largest N digit perfect square in base B`

`function` `largestNDigitPerfectSquare(N, B) {`

`// Largest N digit number in base B is (B^N)-1`

`let largestNum = Math.pow(B, N) - 1;`

`// Check perfect squares starting from the largest number`

`for` `(let i = largestNum; i >= 0; i--) {`

`let decimalNum = 0, count = 0, num = i;`

`while` `(num !== 0) {`

`let rem = num % 10;`

`decimalNum += rem * Math.pow(B, count);`

`count++;`

`num = Math.floor(num / 10);`

`}`

`if` `(isPerfectSquare(decimalNum)) {`

`return` `decimalToBase(decimalNum, B);`

`}`

`}`

`// If no perfect square is found, return -1`

`return` `-1;`

`}`

`let N = 2, B = 10;`

`let largestPerfectSquare = largestNDigitPerfectSquare(N, B);`

`console.log(largestPerfectSquare);`

## C#

`using` `System;`

`class` `Program {`

`// Function to check if a number is a perfect square`

`static` `bool` `isPerfectSquare(``int` `n) {`

`int` `root = (``int``) Math.Sqrt(n);`

`return` `(root * root == n);`

`}`

`// Function to convert decimal to any base`

`static` `int` `decimalToBase(``int` `n, ``int` `b) {`

`int` `num = 0, count = 0;`

`while` `(n != 0) {`

`int` `rem = n % b;`

`num += rem * (``int``) Math.Pow(10, count);`

`count++;`

`n /= b;`

`}`

`return` `num;`

`}`

`// Function to find the largest N digit perfect square in base B`

`static` `int` `largestNDigitPerfectSquare(``int` `N, ``int` `B) {`

`// Largest N digit number in base B is (B^N)-1`

`int` `largestNum = (``int``) Math.Pow(B, N) - 1;`

`// Check perfect squares starting from the largest number`

`for` `(``int` `i = largestNum; i >= 0; i--) {`

`int` `decimalNum = 0, count = 0;`

`int` `num = i;`

`while` `(num != 0) {`

`int` `rem = num % 10;`

`decimalNum += rem * (``int``) Math.Pow(B, count);`

`count++;`

`num /= 10;`

`}`

`if` `(isPerfectSquare(decimalNum)) {`

`return` `decimalToBase(decimalNum, B);`

`}`

`}`

`// If no perfect square is found, return -1`

`return` `-1;`

`}`

`static` `void` `Main(``string``[] args) {`

`int` `N = 2, B = 10;`

`int` `largestPerfectSquare = largestNDigitPerfectSquare(N, B);`

`Console.WriteLine(largestPerfectSquare);`

(Video) Perfect Number | School Practice Problem | GeeksforGeeks School

`}`

`}`

Output

`81`

Time Complexity: O(B^N), where B and N are given in the problem statement
Space Complexity: O(1)

Approach: The largest number N in base B is given by . So if we find the square root of this number in integer form and then we have to again do its square then it will be the largest perfect square of N digits which is given by the formula: .
Below is the implementation of the above approach:

## C++

`// C++ implementation to find Largest`

`// N digit perfect square number in Base B`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to find the`

`// largest N digit number`

`void` `nDigitPerfectSquares(``int` `n, ``int` `b)`

`{`

`// Largest n-digit perfect square`

`int` `largest`

`= ``pow``(``ceil``(``sqrt``(``pow``(b, n))) - 1, 2);`

`// Print the result`

`cout << largest;`

`}`

`// Driver Code`

`int` `main()`

`{`

`int` `N = 1, B = 8;`

`nDigitPerfectSquares(N, B);`

`return` `0;`

`}`

## Java

`// Java implementation to find largest N`

`// digit perfect square number in base B`

`import` `java.io.*;`

`import` `java.util.*;`

`class` `GFG {`

`// Function to find the`

`// largest N digit number`

`static` `double` `nDigitPerfectSquares(``int` `n, ``int` `b)`

`{`

`// Largest n-digit perfect square`

`double` `largest = Math.pow(Math.ceil`

`(Math.sqrt`

`(Math.pow(b, n))) - ``1``, ``2``);`

`// Print the result`

`return` `largest;`

`}`

`// Driver code`

`public` `static` `void` `main(String[] args)`

`{`

`int` `N = ``1``, B = ``8``;`

`System.out.println(nDigitPerfectSquares(N, B));`

`}`

`}`

`// This code is contributed by coder001`

## Python3

`# Python3 implementation to find the largest`

`# N digit perfect square number in base B`

(Video) Find nth Magic Number | GeeksforGeeks

`import` `math`

`# Function to find the`

`# largest N digit number`

`def` `nDigitPerfectSquares(n, b):`

`# Largest n-digit perfect square`

`largest ``=` `pow``(math.ceil`

`(math.sqrt(``pow``(b, n))) ``-` `1``, ``2``)`

`# Print the result`

`print``(largest)`

`# Driver Code`

`N ``=` `1`

`B ``=` `8`

`nDigitPerfectSquares(N, B)`

`# This code is contributed by divyamohan123`

## Javascript

`<script>`

`// Javascript implementation to find Largest`

`// N digit perfect square number in Base B`

`// Function to find the`

`// largest N digit number`

`function` `nDigitPerfectSquares(n, b)`

`{`

`// Largest n-digit perfect square`

`var` `largest`

`= Math.pow(Math.ceil(Math.sqrt(Math.pow(b, n))) - 1, 2);`

`// Print the result`

`document.write(largest);`

`}`

`// Driver Code`

`var` `N = 1, B = 8;`

`nDigitPerfectSquares(N, B);`

`</script>`

## C#

`// C# implementation to find largest N`

`// digit perfect square number in base B`

`using` `System;`

`class` `GFG {`

`// Function to find the`

`// largest N digit number`

`static` `double` `nDigitPerfectSquares(``int` `n, ``int` `b)`

`{`

`// Largest n-digit perfect square`

`double` `largest = Math.Pow(Math.Ceiling`

`(Math.Sqrt`

`(Math.Pow(b, n))) - 1, 2);`

`// Print the result`

`return` `largest;`

`}`

`// Driver code`

`public` `static` `void` `Main(String[] args)`

`{`

`int` `N = 1, B = 8;`

`Console.WriteLine(nDigitPerfectSquares(N, B));`

`}`

`}`

`// This code is contributed by PrinciRaj1992`

Output:

`4`

Time Complexity: O(logn)
Auxiliary Space: O(1)

My Personal Notesarrow_drop_up

Last Updated :03 Apr, 2023

Like Article

Save Article

## FAQs

### How do you find the greatest digit number which is a perfect square? ›

From the division method of square root evaluation, we get remainder as 143. So, this confirms that 99999 is not a perfect square. Now, subtracting 143 from 99999 we get, 99999 – 143 = 99856. Hence, 99856 is the largest five- digit perfect square number.

What is the greatest six digit natural number which is a perfect square? ›

Thus, the largest 6 digit perfect square is 998001=(999)2.

Which is the greatest 4 digit perfect square a 9999 b 9990 c 9800 d 9801? ›

∴ Greatest 4 digit number that is a perfect square = 9999 - 198 = 9801.

Which is the greatest three digit perfect square a 999 b 961 c 962 d 970? ›

Hence, the greatest three-digit number which is a perfect square = 999 - 38 = 961.

What are the largest perfect square numbers? ›

Note that the factor 16 is the largest perfect square. Recall that the numbers 1, 4, 9, 16, 25, 36, 49, … are perfect squares.

What is the greatest 5 digit number which is a perfect square answer? ›

We know that the largest five digit number is 99999. So let us check whether it is a perfect or not ? So here we can see that 99999 is not a perfect square as it leaves 143 as the remainder while finding it square root. Hence 99856 is a perfect square whose square root is √99856 = 316.

What is the largest 7 digit perfect square? ›

so, 9998244 is the greatest 7 digit perfect square.

What are the perfect square digit numbers? ›

Informally: When you multiply an integer (a “whole” number, positive, negative or zero) times itself, the resulting product is called a square number, or a perfect square or simply “a square.” So, 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, and so on, are all square numbers.

What is the least 6 digit number which is a perfect square solution? ›

So, the smallest 6 digit perfect square is 100489.

What is the greatest 4 digit number which is a perfect square in base 8? ›

In base 8, the largest number is 7777. It is equivalent to 4095 in decimal. The perfect square it is close to is 4096 = 64x64 and 3969 = 63x63. So the greatest four digit number which is a perfect square is 7601.

### What is the greatest perfect square of 4 digits in base 9? ›

So n=92−1=80 and n2=802 is the largest four digit perfect square. 87018. The largest four digit perfect square is 802=8829=87018.

What is the greatest 4 digit number which is a perfect square root? ›

9801 is the required greatest 4 digit perfect square number.

How do you find the largest 3 digit number which is a perfect square? ›

∴ The greatest 3 digit number which is a perfect square =999-38= 961.

What is the greatest 4 digit perfect square which is exactly divisible by 3 5 and 7 and 9? ›

The number divisible by 3, 5, 7, and 9 will be its LCM or its multiples. So, to get the required number that will leave the above-said remainders, we need to subtract 2 from 9765. Required number = 9765 - 2 = 9763.

Is 9999 a perfect square? ›

The largest 4 digit number is 9999 which is not a perfect square.

Is 994009 a perfect square? ›

It is not a perfect square.

What is the largest perfect square of 72? ›

Is 1600 a perfect square? ›

Yes, 1600 is a perfect square. A perfect square is a number that can be expressed as the square of a number and 40 × 40 = 1600.

Is any 6 digit perfect square? ›

998001 is the largest six – digit number that is a perfect square.

What is the largest 5 digit number? ›

Five Digit Numbers

The smallest five-digit number is 10000 and the greatest five-digit number is 99999.

### How do I solve perfect squares? ›

1. Step 1: Divide the equation by a. ...
2. Step 2: Move the constant term to the right side of the equation. ...
3. Step 3: Take half of the coefficient for x and square it. ...
4. Step 4: Add the square to both sides of the equation. ...
5. Step 5: Factor the perfect square trinomial. ...
6. Step 6: Take the square root of both sides.

What is the largest 8 digit perfect square? ›

largest eight digit perfect square no. Is 81000000.

Which is the 2 digit largest perfect square? ›

81 is the greatest two digit number which is a perfect square. Q. Find the greatest number of two digits which is a perfect square.

What is the largest 2 digit number which is a perfect square solution? ›

Hence largest two digit number who is also a perfect square = 81. Q.

Is 99 the 2 digit greatest perfect square number? ›

The aim is to find the greatest number of two digits which is a perfect square. As we know that 9 is the greatest digit of all the digits so we will form a 2-digit number. Hence, 99 is the greatest two-digit number.

What is the least 7 digit number which is a perfect square? ›

Smallest 7digit number is 1000000 and it already is a perfect square. Hope it helps.

What is the largest 6 digit number? ›

Largest 6 digit number is 999990.

What are perfect 4 digit squares? ›

And, also the numbers 1020, 1021, 1022, 1023, 1027, 10 do not qualify the above criteria, so the numbers between 1020 to 1029 which are left out are 1024, 1025, 1026, 1029. Hence, The smallest four digit number which is a perfect square is 1024. Note: A squares of all integers are called as perfect square numbers.

What are the 8 perfect square numbers? ›

The perfect squares are the squares of the whole numbers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 … So, from above given numbers, 1, 36, 49, 81, 169, 625, 900 and 100 are perfect squares.

What is the greatest 4-digit perfect square in base 7? ›

It's square (in base 7 system) is 6501. Thus, 6501 is the greatest 4-digit perfect square in base 7 system.

### What is the smallest 4-digit number which is a perfect square root? ›

Hence, 1024 is the smallest four-digit number which is a perfect square.

Which is the smallest perfect square number which is divisible b 4 9 and 10? ›

Hence, 900 is the smallest square number divisible by each one of the numbers 4 , 9 and 10.

What is the last 4 digit perfect square? ›

9999 - 198 = 9801 is required perfect square.

What is a perfect square greater than 4? ›

The first 20 perfect square numbers are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, and 400.

How to find the largest 4 digit number which is a perfect cube? ›

As the cube of 22 is a five-digit number, the largest four-digit number which is a perfect cube is the cube root of 21. So, the required number is 9261.

How do you find the largest 3 digit number? ›

Which Is the Largest 3 Digit Number? The largest 3 digit number is 999. The smallest 3 digit number is 100.

How do you find the smallest 3 digit perfect square? ›

We see that 100 is the least three digit number which is a perfect square.

How to find the least square number which is exactly divisible by 3 4 5 6 and 8? ›

The least square number which is exactly divisible by 3, 4, 5, 6 and 8 is 3600.

What is the least perfect square number divisible by 3 4 5 6 8? ›

∴ 3600 is the least perfect square divisible by 3, 4, 5, 6 and 8.

What is the smallest perfect square divisible by 3 4 5 and 6 question 11? ›

Hence, the smallest perfect square divisible by 3,4 5 and 6 is 900.

### Why 1234 is not a perfect square? ›

All perfect squares end in 1, 4, 5, 6, 9 or 00 (i.e. Even number of zeros). Therefore, a number that ends in 2, 3, 7 or 8 is not a perfect square.

Is 900 a perfect square? ›

The square root of 900 is expressed as √900 in the radical form and as (900)½ or (900)0.5 in the exponent form. The square root of 900 is 30. It is the positive solution of the equation x2 = 900. The number 900 is a perfect square.

Why is 99 not a perfect square? ›

Now, 99 is not a perfect square number because we cannot find any integer which could be multiplied twice to get 99. Thus, we find an approximate value of the square root of 99, as it is an irrational number.

How do you find which number is a perfect square? ›

A number is a perfect square (or a square number) if its square root is an integer; that is to say, it is the product of an integer with itself. A number that is a perfect square never ends in 2, 3, 7 or 8.

What is the greater number of two digits which is a perfect square? ›

Hence largest two digit number who is also a perfect square = 81. Q.

How do you find the perfect square number of a number? ›

How to Find Perfect Square? To find a perfect square, we need to multiply the whole number by itself. The first 20 perfect square numbers are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, and 400.

How do you know if a digit is a perfect square? ›

All perfect squares end in 1, 4, 5, 6, 9 or 00 (i.e. Even number of zeros). Therefore, a number that ends in 2, 3, 7 or 8 is not a perfect square.

Is 32 a perfect square? ›

32 is not a perfect square.

Which is the perfect square number between 1 to 100? ›

Therefore, the number of perfect squares between 1 to 100 natural numbers is 9.

What is the three digit largest perfect square? ›

∴ The greatest 3 digit number which is a perfect square =999-38= 961.

### Which are the smallest and largest 2-digit perfect squares? ›

Smallest 2-digit perfect square is 16 and the largest 2-digit perfect square is 81.

What is the greatest number of 7 digits which is a perfect square? ›

so, 9998244 is the greatest 7 digit perfect square.

What are the 4 digit perfect square numbers examples? ›

Therefore we can say that the square of 99 is the number which gives the greatest four digits number. And therefore 9801 is the greatest four digit number which is a perfect square.

How many 2 digit numbers are perfect squares? ›

So, there are 17 two-digit numbers whose sum of digits is a perfect square. Note: Perfect squares are those numbers which are formed when any number is multiplied by itself.

What is the rule of perfect square last digit? ›

Here are some important properties of perfect square numbers: The last digit is 0, 1, 4, 5, 6, or 9. The digital root is always 1, 4, 7, 9. If the last digit is 6, then the penultimate digit must be odd.

## Videos

1. Greatest of Three Numbers | School Practice Problem | GeeksforGeeks School
(GeeksforGeeks School)
2. Leetcode Weekly Contest 238 | Problem 1837 , 1838 , 1839 | Leetcode | CODE EXPLAINER
(code Explainer)
3. Find the smallest missing number | GeeksforGeeks
(GeeksforGeeks)
4. ✨GFG Weekly Coding Contest - 100 [Special Edition]✨ Post Analysis | GeeksforGeeks Practice
(GeeksforGeeks Practice)
5. Practice Session for SDE Interviews: Essential Maths (Part - 1) | GeeksforGeeks Practice
(GeeksforGeeks Practice)
6. Print a given matrix in spiral form | GeeksforGeeks
(GeeksforGeeks)
Top Articles
Latest Posts
Article information

Author: Roderick King

Last Updated: 05/21/2023

Views: 5966

Rating: 4 / 5 (51 voted)

Author information

Name: Roderick King

Birthday: 1997-10-09