367 Valid Perfect Square
Given a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any built-in library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14 Returns: False
```c++
bool isPerfectSquare(int num) {
return sqrt(num) == int(sqrt(num));
}
- Assumming I only have to do this once, I would use a for loop to calculate the square. Otherwise, I would calculate all the perfect squares into a hash table, and use this as my look up table.
// too slow
int power(int number, int pow) {
int mult = 1;
for (int i = 0; i < pow; i++) {
mult *= number;
}
return mult;
}
bool isPerfectSquare(int num) {
// all powers of 2 are perfect squares
int cur_power = 1;
for (int i = 2; i < num; i++) {
if (num == cur_power) return true;
else if (cur_power > num) return false;
cur_power = power(i, 2);
}
}
int main() {
cout << boolalpha << isPerfectSquare(1) << endl;
cout << boolalpha << isPerfectSquare(2) << endl;
cout << boolalpha << isPerfectSquare(64) << endl;
cout << boolalpha << isPerfectSquare(2147483647) << endl;
}
Last modified 4yr ago