**Problem:**

Please find the problem here.

**Analysis:**

It is really easy to write a solution based on the identity

$ n^2 = \sum\limits_{i=1}^{n}{(2i - 1)} $

Just subtract the odd numbers one by one, if we reach 0, then it is a perfect square. If it is negative, then it is not.

The complexity of the solution above is $ O(\sqrt{n}) $, can we do better?

**Solution:**

We can binary search for the square root. That requires multiplication, but only a handful of them because $ O(\log n) $ is really small. Care is taken in the code to make sure we do not overflow.

**Code:**

#include "stdafx.h" // https://leetcode.com/problems/valid-perfect-square/ #include "LEET_VALID_PERFECT_SQUARE.h" #include <map> #include <iostream> #include <sstream> #include <vector> #include <string> using namespace std; namespace _LEET_VALID_PERFECT_SQUARE { class Solution { public: bool isPerfectSquare(int num) { if (num == 0) { return true; } if (num == 1) { return true; } int exclusiveLowerBound = 0; int exclusiveUpperBound = num; while (exclusiveUpperBound - exclusiveLowerBound > 1) { // Note: this will never overflow // This will also always return a value strictly between the two bounds int mid = (exclusiveLowerBound + exclusiveUpperBound) / 2; // Squaring could overflow, so using 64 bit arithmetic here long long midl = (long long)mid; long long square = midl * midl; if (square < num) { exclusiveLowerBound = mid; } else if (square > num) { exclusiveUpperBound = mid; } else { return true; } } return false; } }; }; using namespace _LEET_VALID_PERFECT_SQUARE; int LEET_VALID_PERFECT_SQUARE() { Solution s; cout << s.isPerfectSquare(899 * 899) << endl; return 0; }

## No comments :

## Post a Comment