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;
}
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) {
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);
}
}
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
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? ›=62. Was this answer helpful?
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? ›
- Step 1: Divide the equation by a. ...
- Step 2: Move the constant term to the right side of the equation. ...
- Step 3: Take half of the coefficient for x and square it. ...
- Step 4: Add the square to both sides of the equation. ...
- Step 5: Factor the perfect square trinomial. ...
- Step 6: Take the square root of both sides.
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.