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 updated