Count square and non-square numbers before n
Given a number n, we need to count square numbers smaller than or equal to n.
Examples :
Input : n = 5 Output : Square Number : 2 Non-square numbers : 3 Explanation : Square numbers are 1 and 4. Non square numbers are 2, 3 and 5. Input : n = 10 Output : Square Number : 3 Non-square numbers : 7 Explanation : Square numbers are 1, 4 and 9. Non square numbers are 2, 3, 5, 6, 7, 8 and 10.
A simple solution is to traverse through all numbers from 1 to n and for every number check if n is perfect square or not.
An efficient solution is based on below formula.
Count of square numbers that are greater than 0 and smaller than or equal to n are floor(sqrt(n)) or ??(n)?
Count of non-square numbers = n – ??(n)?
C++
// CPP program to count squares and // non-squares before a number. #include <bits/stdc++.h> using namespace std; void countSquaresNonSquares( int n) { int sc = floor ( sqrt (n)); cout << "Count of squares " << sc << endl; cout << "Count of non-squares " << n - sc << endl; } // Driver Code int main() { int n = 10; countSquaresNonSquares(n); return 0; } |
Java
// Java program to count squares and // non-squares before a number. import java.io.*; import java.math.*; class GFG { static void countSquaresNonSquares( int n) { int sc = ( int )(Math.floor(Math.sqrt(n))); System.out.println( "Count of" + " squares " + sc); System.out.println( "Count of" + " non-squares " + (n - sc) ); } // Driver code public static void main(String args[]) { int n = 10 ; countSquaresNonSquares(n); } } // This code is contributed // by Nikita Tiwari. |
Python3
# Python 3 program to count # squares and non-squares # before a number. import math def countSquaresNonSquares(n) : sc = (math.floor(math.sqrt(n))) print ( "Count of squares " , sc) print ( "Count of non-squares " , (n - sc) ) # Driver code n = 10 countSquaresNonSquares(n) # This code is contributed # by Nikita Tiwari. |
C#
// C# program to count squares and // non-squares before a number. using System; class GFG { static void countSquaresNonSquares( int n) { int sc = ( int )Math.Sqrt(n); Console.WriteLine( "Count of " + "squares " + sc) ; Console.WriteLine( "Count of " + "non-squares " + (n - sc)); } // Driver Code static public void Main () { int n = 10; countSquaresNonSquares(n); } } // This code is contributed by anuj_67. |
PHP
<?php // PHP program to count // squares and non-squares // before a number. // function to count squares // and non-squares before a // number function countSquaresNonSquares( $n ) { $sc = floor (sqrt( $n )); echo ( "Count of squares " . $sc . "\n" ); echo ( "Count of non-squares " . ( $n - $sc )); } // Driver code $n = 10; countSquaresNonSquares( $n ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to count squares and // non-squares before a number. function countSquaresNonSquares(n) { let sc = Math.floor(Math.sqrt(n)); document.write( "Count of squares " + sc + "<br>" ); document.write( "Count of non-squares " + (n - sc) + "<br>" ); } // Driver Code let n = 10; countSquaresNonSquares(n); //This code is contributed by Mayank Tyagi </script> |
Output :
Count of squares 3 Count of non-squares 7
Time Complexity: O(logn)
Auxiliary Space: O(1) as using only constant variables
Approach 2: Using Loops:
Another approach to count the number of squares and non-squares before a given number is to iterate over all the numbers from 1 to n and check if each number is a perfect square or not. If a number is a perfect square, we increment the count of squares, otherwise, we increment the count of non-squares.
Here’s the code implementing this approach:
C++
#include <iostream> #include <cmath> void countSquaresNonSquares( int n) { int countSquares = 0; int countNonSquares = 0; for ( int i = 1; i <= n; i++) { int sqrtI = std:: sqrt (i); if (sqrtI * sqrtI == i) { countSquares++; } else { countNonSquares++; } } std::cout << "Count of squares " << countSquares << std::endl; std::cout << "Count of non-squares " << countNonSquares << std::endl; } int main() { int n = 10; countSquaresNonSquares(n); return 0; } |
Java
import java.util.*; public class Main { public static void countSquaresNonSquares( int n) { int countSquares = 0 ; int countNonSquares = 0 ; for ( int i = 1 ; i <= n; i++) { int sqrtI = ( int )Math.sqrt(i); if (sqrtI * sqrtI == i) { countSquares++; } else { countNonSquares++; } } System.out.println( "Count of squares " + countSquares); System.out.println( "Count of non-squares " + countNonSquares); } public static void main(String[] args) { int n = 10 ; countSquaresNonSquares(n); } } |
Python3
import math def countSquaresNonSquares(n): countSquares = 0 countNonSquares = 0 for i in range ( 1 , n + 1 ): sqrtI = int (math.sqrt(i)) if sqrtI * sqrtI = = i: countSquares + = 1 else : countNonSquares + = 1 print ( "Count of squares" , countSquares) print ( "Count of non-squares" , countNonSquares) n = 10 countSquaresNonSquares(n) |
C#
using System; class MainClass { public static void countSquaresNonSquares( int n) { int countSquares = 0; int countNonSquares = 0; for ( int i = 1; i <= n; i++) { int sqrtI = ( int )Math.Sqrt(i); if (sqrtI * sqrtI == i) { countSquares++; } else { countNonSquares++; } } Console.WriteLine( "Count of squares: " + countSquares); Console.WriteLine( "Count of non-squares: " + countNonSquares); } public static void Main() { int n = 10; countSquaresNonSquares(n); } } |
Javascript
function countSquaresNonSquares(n) { let countSquares = 0; let countNonSquares = 0; for (let i = 1; i <= n; i++) { let sqrtI = Math.sqrt(i); if (sqrtI * sqrtI === i) { countSquares++; } else { countNonSquares++; } } console.log( "Count of squares " + countSquares); console.log( "Count of non-squares " + countNonSquares); } let n = 10; // function Call countSquaresNonSquares(n); // This code is contributed by shivhack999 |
Output :
Count of squares 3 Count of non-squares 7
Time Complexity: O(nsqrt(n)), where n is the input variable, as described in the problem statement
Auxiliary Space: O(1) as using only constant variables