ConsultTheOrb
BAN USERclass CountSquares
{
public static boolean isSquare(int n)
{
return Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n));
}
public static int countSquaresNaive(int n)
{
if (n <= 1) {
return n;
}
int minCount = Integer.MAX_VALUE;
for (int i=n; i>=1; i--) {
if (isSquare(i)) {
int c = 1 + countSquaresNaive(n - i);
if (c < minCount) {
minCount = c;
}
}
}
return minCount;
}
public static int countSquaresDP(int n)
{
if (n <= 1) {
return n;
}
int[] L = new int[n+1];
for (int i=0; i<L.length; i++) {
L[i] = 0;
}
L[0] = 0;
L[1] = 1;
for (int i=2; i<=n; i++) {
if (isSquare(i)) {
L[i] = 1;
} else {
int minCount = Integer.MAX_VALUE;
int k = i / 2;
for (int j=i-1; j>=k; j--) {
minCount = Math.min(minCount, L[j] + L[i-j]);
if (minCount <= 2) {
break;
}
}
L[i] = minCount;
}
}
return L[n];
}
public static void main(String[] args)
{
for (int i=0; i<=50; i++) {
int a = countSquaresNaive(i);
int b = countSquaresDP(i);
assert a == b;
System.out.println("countSquaresNaive("+i+") = "+a+", countSquaresDP("+i+") = "+b);
}
}
}
Repjuliaaperez05, Cloud Support Associate at ABC TECH SUPPORT
I Performed extensive web research to collect pertinent data and gather images related to the assigned articleIts act of writing ...
Replisaramsey773, Blockchain Developer at Adjetter Media Network Pvt Ltd.
I'm a 27 year-old blogger, make-up junkie and follower of Christ.I love all things that bring happiness. My ...
Repjanicepdaniels1, Backend Developer at Accenture
I decided to become an entrepreneur and work for myself because I wasn't making the money I wanted to ...
Repwilliamchansen95, Computer Scientist at 247quickbookshelp
I am working as a manager in Lionel Kiddie City company. I really enjoy my job. I like to play ...
A verbose, but simple ripple-carry implementation:
- ConsultTheOrb March 19, 2015