Wednesday, September 9, 2015

LeetCode OJ - Perfect Squares

Problem:

Solution:

Lagrange's four square theorem helps us a big way here. The theorem states that any natural number can be written as a sum of four squares, so all we need to do is to test if it is writable a square, a sum of two squares or three squares, otherwise we just simply conclude it is four squares.

Part of the code can still be optimized, don't bother ...

Code:

#include "stdafx.h"

// https://leetcode.com/problems/perfect-squares/

#include "LEET_PERFECT_SQUARES.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_PERFECT_SQUARES
{
class Solution
{
private:
bool isSquare(int n)
{
for (int i = 1; i * i <= n; i++)
{
if (i * i == n)
{
return true;
}
}

return false;
}
bool isTwoSquare(int n)
{
for (int i = 1; i * i < n; i++)
{
int s = i * i;
int r = n - s;
if (isSquare(r))
{
return true;
}
}

return false;
}
bool isThreeSquare(int n)
{
for (int i = 1; i * i < n; i++)
{
int s = i * i;
int r = n - s;
if (isTwoSquare(r))
{
return true;
}
}

return false;
}
public:
int numSquares(int n)
{
if (isSquare(n))
{
return 1;
}
else if (isTwoSquare(n))
{
return 2;
}
else if (isThreeSquare(n))
{
return 3;
}
else
{
return 4;
}

}
};
};

using namespace _LEET_PERFECT_SQUARES;

int LEET_PERFECT_SQUARES()
{
Solution s;
for (int i = 1; i <= 10000; i++)
{
cout << i << " " << s.numSquares(i) << endl;
}
return 0;
}