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 10N – 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 squarebool 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 squaresint 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 codeint main(){ int n = 3; cout << countSquares(n); return 0;} |
Java
// Java Program to count perfect// squares of given lengthimport java.io.*;import java.util.*;class GFG{// Function to check if a// number is perfect squarestatic 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 squaresstatic 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 codepublic 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 lengthimport math;# Function to check if a# number is perfect squaredef 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 squaresdef 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 coden = 3;print(countSquares(n));# This code is contributed by Akanksha_Rai |
C#
// C# program to count perfect// squares of given lengthusing System;class GFG{// Function to check if a// number is perfect squarestatic 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 squaresstatic 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 codepublic 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 squarefunction 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 squaresfunction 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 codelet n = 3;document.write(countSquares(n));// This code is contributed by subhammahato348.</script> |
Output:
22
Time Complexity: O(10n*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
- Hence, a perfect square n2 has d digits if
or 
- Thus, the required answer for count of perfect squares of N digits is
or 
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 squaresint countSquares(int n){ int r = ceil(sqrt(pow(10, n))); int l = ceil(sqrt(pow(10, n - 1))); return r - l;}// Driver codeint main(){ int n = 3; cout << countSquares(n); return 0;} |
Java
// Java Program to count perfect // squares of given lengthimport java.io.*;import java.util.*;class GFG{// Function to return the count // of n digit perfect squaresstatic 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 codepublic 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 lengthusing System;class GFG{// Function to return the count // of n digit perfect squaresstatic 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 codepublic 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 squaresfunction 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 codelet n = 3;document.write(countSquares(n));</script> |
Output:
22
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
