Problem
Write a program to find whether a given number is a perfect square or not. You can only use addition and subtraction operation to find a solution with min. complexity.
i/p : 25
o/p : True
i/p : 44
o/p: False
Solution
#include <iostream>
#include <iomanip>
using namespace std;
bool IsPerfectSquare(int num)
{
if(num < 0){
return false;
}
if(num < 2){
return true;
}
int i = 1;
int sum = 0;
while(sum < num){
sum += i;
i += 2;
}
return sum == num;
}
int main(int argc, char* argv[])
{
for(int i = -1; i < 40; ++i){
cout << left << setw(3) << i;
if(IsPerfectSquare(i)){
cout << " is perfect square number. " << endl;
}
else{
cout << " is NOT perfect sqaure number." << endl;
}
}
return 0;
}
Output
-1 is NOT perfect sqaure number.
0 is perfect square number.
1 is perfect square number.
2 is NOT perfect sqaure number.
3 is NOT perfect sqaure number.
4 is perfect square number.
5 is NOT perfect sqaure number.
6 is NOT perfect sqaure number.
7 is NOT perfect sqaure number.
8 is NOT perfect sqaure number.
9 is perfect square number.
10 is NOT perfect sqaure number.
11 is NOT perfect sqaure number.
12 is NOT perfect sqaure number.
13 is NOT perfect sqaure number.
14 is NOT perfect sqaure number.
15 is NOT perfect sqaure number.
16 is perfect square number.
17 is NOT perfect sqaure number.
18 is NOT perfect sqaure number.
19 is NOT perfect sqaure number.
20 is NOT perfect sqaure number.
21 is NOT perfect sqaure number.
22 is NOT perfect sqaure number.
23 is NOT perfect sqaure number.
24 is NOT perfect sqaure number.
25 is perfect square number.
26 is NOT perfect sqaure number.
27 is NOT perfect sqaure number.
28 is NOT perfect sqaure number.
29 is NOT perfect sqaure number.
30 is NOT perfect sqaure number.
31 is NOT perfect sqaure number.
32 is NOT perfect sqaure number.
33 is NOT perfect sqaure number.
34 is NOT perfect sqaure number.
35 is NOT perfect sqaure number.
36 is perfect square number.
37 is NOT perfect sqaure number.
38 is NOT perfect sqaure number.
39 is NOT perfect sqaure number.
Press any key to continue . . .