Count Square and Non-Square Numbers Before N in C++

We are given a number N. The goal is to find ordered pairs of positive numbers such that the sum of their cubes is N.

Naive Approach

Traverse all numbers from 1 to N and check if it is a perfect square. If floor(sqrt(i))==ceil(sqrt(i)).

Then the number is a perfect square.

Efficient Approach

Perfect squares below N can be found using formula: floor(sqrt(N)).

Let’s understand with examples.

Input 

N=20

Output 

Count of square numbers: 4
Count of non-square numbers: 16

Explanation 

Square numbers are 1, 4, 9 and 16. Rest all are non-squares and less than 20.

Input 

N=40

Output 

Count of square numbers: 6
Count of non-square numbers: 34

Explanation 

Square numbers are 1, 4, 9, 16, 25, 36. Rest all are non-squares and less than 40.

Naive Approach

Approach used in the below program is as follows

• We take integer N.

• Function squareNums(int n) takes n and returns the count of numbers below n that are perfect squares or non-squares.

• Take the initial variable count as 0.

• Traverse using for loop from i=1 to i<=n

• If floor(sqrt(i))==ceil(sqrt(i)), then the number is a perfect square so increment count.

• At the end of all loops count will have a total number that are perfect squares.

• N-squares will be numbers that are non squares

Example

 Live Demo

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareNums(int n){
   int count = 0;
   for (int i = 1; i <= n; i++){
      if(floor(sqrt(i))==ceil(sqrt(i)))
         { count++; }
   }
   return count;
}
int main(){
   int N = 40;
   int squares=squareNums(N);
   cout <<endl<<"Count of squares numbers: "<<squares;
   cout <<endl<<"Count of non-squares numbers: "<<N-squares;
   return 0;
}

Output

If we run the above code it will generate the following output −

Count of squares numbers: 6
Count of non-squares numbers: 34

Efficient Approach

Approach used in the below program is as follows

• We take integer N.

• Take variable squares = floor(sqrt(N)).

• Variable squares will have a number of perfect squares below N.

• N-squares will be the number of non-squares below N.

Example

 Live Demo

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
   int N = 40;
   int squares=floor(sqrt(N));
   cout <<endl<<"Count of squares numbers: "<<squares;
   cout <<endl<<"Count of non-squares numbers: "<<N-squares;
   return 0;
}

Output

If we run the above code it will generate the following output −

Count of squares numbers: 6
Count of non-squares numbers: 34