## Sunday, June 26, 2016

### LeetCode OJ - Valid Perfect Square

Problem:

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;
}