Count of perfect squares of given length

0 0 5 minutes read

Given an integer N, the task is to find the number of perfect squares of length N.
Examples:

Input: N = 1
Output: 3
Explanation: The single digit perfect squares are 1, 4 and 9.

Input: N = 2
Output: 6
Explanation: The two-digit perfect squares are 16, 25, 36, 49, 64 and 81.

Naive Approach: In order to solve this problem, we can check all the numbers between 10^{( N – 1 )} and 10^N – 1 and increment the counter whenever we encounter a perfect square.
Below is the implementation of the above approach:

C++

// C++ Program to count perfect
// squares of given length
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is perfect square
bool isPerfectSquare(long double x)
{
    // Find floating point value of
    // square root of x.
    long double sr = sqrt(x);
 
    // If square root is an integer
    return ((sr - floor(sr)) == 0);
}
 
// Function to return the count of
// n digit perfect squares
int countSquares(int n)
{
    // Initialize result
    int cnt = 0;
 
    // Traverse through all numbers
    // of n digits
    for (int i = pow(10, (n - 1));
         i < pow(10, n); i++) {
 
        // Check if current number
        // 'i' is perfect square
        if (i != 0 && isPerfectSquare(i))
            cnt++;
    }
    return cnt;
}
 
// Driver code
int main()
{
    int n = 3;
    cout << countSquares(n);
    return 0;
}

Java

// Java Program to count perfect
// squares of given length
import java.io.*;
import java.util.*;
class GFG{
 
// Function to check if a
// number is perfect square
static boolean isPerfectSquare(double x)
{
     
    // Find floating point value of
    // square root of x.
    double sr = Math.sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function to return the count of
// n digit perfect squares
static int countSquares(int n)
{
     
    // Initialize result
    int cnt = 0;
 
    // Traverse through all numbers
    // of n digits
    for(int i = (int) Math.pow(10, (n - 1));
                  i < Math.pow(10, n); i++) 
    {
 
        // Check if current number
        // 'i' is perfect square
        if (i != 0 && isPerfectSquare(i))
            cnt++;
    }
    return cnt;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
    System.out.print(countSquares(n));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 Program to count perfect
# squares of given length
import math;
 
# Function to check if a
# number is perfect square
def isPerfectSquare(x):
 
    # Find floating point value of
    # square root of x.
    sr = math.sqrt(x);
 
    # If square root is an integer
    return ((sr - math.floor(sr)) == 0);
 
# Function to return the count of
# n digit perfect squares
def countSquares(n):
 
    # Initialize result
    cnt = 0;
 
    # Traverse through all numbers
    # of n digits
    for i in range(int(math.pow(10, (n - 1))), 
                   int(math.pow(10, n))):
 
        # Check if current number
        # 'i' is perfect square
        if (i != 0 and isPerfectSquare(i)):
            cnt += 1;
     
    return cnt;
 
# Driver code
n = 3;
print(countSquares(n));
 
# This code is contributed by Akanksha_Rai

C#

// C# program to count perfect
// squares of given length
using System;
 
class GFG{
 
// Function to check if a
// number is perfect square
static bool isPerfectSquare(double x)
{
     
    // Find floating point value of
    // square root of x.
    double sr = Math.Sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.Floor(sr)) == 0);
}
 
// Function to return the count of
// n digit perfect squares
static int countSquares(int n)
{
     
    // Initialize result
    int cnt = 0;
 
    // Traverse through all numbers
    // of n digits
    for(int i = (int) Math.Pow(10, (n - 1));
                  i < Math.Pow(10, n); i++) 
    {
 
       // Check if current number
       // 'i' is perfect square
       if (i != 0 && isPerfectSquare(i))
           cnt++;
    }
    return cnt;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 3;
     
    Console.Write(countSquares(n));
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
// Javascript Program to count perfect
// squares of given length
 
// Function to check if a
// number is perfect square
function isPerfectSquare(x)
{
    // Find floating point value of
    // square root of x.
    let sr = Math.sqrt(x);
 
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function to return the count of
// n digit perfect squares
function countSquares(n)
{
    // Initialize result
    let cnt = 0;
 
    // Traverse through all numbers
    // of n digits
    for (let i = Math.pow(10, (n - 1));
         i < Math.pow(10, n); i++) {
 
        // Check if current number
        // 'i' is perfect square
        if (i != 0 && isPerfectSquare(i))
            cnt++;
    }
    return cnt;
}
 
// Driver code
let n = 3;
document.write(countSquares(n));
 
// This code is contributed by subhammahato348.
</script>

Output:

Time Complexity: O(10ⁿ*log(n))
Auxiliary Space: O(1)

Efficient Approach: In order to solve this problem we can simply find the number of perfect squares of length N using a formula:

A number n has d digits if ${10}^{d-1}\le n< {10}^{d}$
Hence, a perfect square n² has d digits if ${10}^{d-1}\le {n}^{2}< {10}^{d}$ or $\sqrt{10}^{d-1}\le n<\sqrt{10}^d.$
Thus, the required answer for count of perfect squares of N digits is $\left\lceil\sqrt{10^N}\right\rceil-\left\lceil\sqrt{10^{N-1}}\right\rceil$

Below is the implementation of the above approach:

C++

// C++ Program to count
// perfect squares of given length
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// n digit perfect squares
int countSquares(int n)
{
    int r = ceil(sqrt(pow(10, n)));
    int l = ceil(sqrt(pow(10, n - 1)));
    return r - l;
}
 
// Driver code
int main()
{
    int n = 3;
    cout << countSquares(n);
    return 0;
}

Java

// Java Program to count perfect 
// squares of given length
import java.io.*;
import java.util.*;
class GFG{
 
// Function to return the count 
// of n digit perfect squares
static int countSquares(int n)
{
    int r = (int) Math.ceil(Math.sqrt
                           (Math.pow(10, n)));
    int l = (int) Math.ceil(Math.sqrt
                           (Math.pow(10, n - 1)));
    return r - l;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
    System.out.print(countSquares(n));
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program to count perfect  
# squares of given length 
import math
 
# Function to return the count
# of n digit perfect squares 
def countSquares(n): 
 
    r = math.ceil(math.sqrt
                 (math.pow(10, n))); 
    l = math.ceil(math.sqrt
                 (math.pow(10, n - 1))); 
     
    return r - l; 
     
# Driver code 
n = 3; 
print(countSquares(n)); 
 
# This code is contributed by grand_master

C#

// C# Program to count perfect 
// squares of given length
using System;
class GFG{
 
// Function to return the count 
// of n digit perfect squares
static int countSquares(int n)
{
    int r = (int) Math.Ceiling(Math.Sqrt
                              (Math.Pow(10, n)));
    int l = (int) Math.Ceiling(Math.Sqrt
                              (Math.Pow(10, n - 1)));
    return r - l;
}
 
// Driver code
public static void Main()
{
    int n = 3;
    Console.Write(countSquares(n));
}
}
 
// This code is contributed by Nidhi_Biet

Javascript

<script>
 
// JavaScript Program to count
// perfect squares of given length
 
// Function to return the count of
// n digit perfect squares
function countSquares(n)
{
    let r = Math.ceil(Math.sqrt(Math.pow(10, n)));
    let l = Math.ceil(Math.sqrt(Math.pow(10, n - 1)));
    return r - l;
}
 
// Driver code
let n = 3;
document.write(countSquares(n));
 
</script>

Output:

Time Complexity: O(log N)
Auxiliary Space: O(1)

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!