Find minimum number K such that given integer N can be represented by K number of squares

You are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 2^2 + 2^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)

See the comment on the top of the code... Sorry just don't bother to type them again...

/**
 * You are given a positive integer number N. 
 * Return the minimum number K, such that N can be 
 * represented as K integer squares. 
 * Examples: 
 * 9 --> 1 (9 = 3^2) 
 * 8 --> 2 (8 = 2^2 + 2^2) 
 * 15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2) 
 * First reach a solution without any assumptions, 
 * then you can improve it using this mathematical lemma (Lagrange's four-square theorem): 
 * For any positive integer N, there is at least one representation 
 * of N as 4 or less squares.
 * N = a^2 + b^2 + c^2 + d^2 such that
 * a >= b >= c >= d
 * a : {floor(sqrt(N)), ceil(sqrt(N / 4))}
 * b : {floor(sqrt(N - a * a)), ceil(sqrt((N - a * a)/3)}
 * c : {floor(sqrt(N - a * a - b * b)), ceil(sqrt((N - a * a - b* b)/2))}
 * d : N - a * a - b * b - c * c
 * if we can find a and b, then if sqrt(N - a * a - b * b) is an integer
 * we have our 3rd integer, thus we don't have to loop to find c
 * if we cannot find a, b, c such that a * a + b * b + c * c = N
 * then we need the 4th integer
 * So the complexity is O(sqrt(N) * sqrt(N)), which is O(N)
 * @author shirleyyoung
 *
 */
public class KIntegerSquares {
 public static int kSquares(int N) {
  if (N < 0)
   throw new IllegalArgumentException("Input must be positive!");
  int sqrt = (int)Math.sqrt(N);
  if (sqrt * sqrt == N)
   return 1;
  int aUpper = (int)Math.sqrt(N);
  int aLower = (int)Math.ceil(Math.sqrt(N / 4.0));
  for (int a = aUpper; a >= aLower; a--) {
   int bUpper = (int)Math.sqrt(N - a * a);
   int bLower = (int)Math.ceil(Math.sqrt((N - a * a) / 3.0));
   for (int b = bUpper; b >= bLower; b--) {
    int currSum = a * a + b * b;
    if (currSum == N)
     return 2;
    double c = Math.sqrt(N - currSum);
    if (c == Math.floor(c))
     return 3;
   }
  }
  return 4;
 }

 public static void main(String[] args) {
  System.out.println(kSquares(31));
 }
}

Update 2015 - 03 - 16
A DP solution that is much easier to understand. Note recursion will not work since it follows a greedy approach which may not give the best answer.

public static int kSquares3(int N){
  if(N < 0)
   throw new IllegalArgumentException("Input must be greater than 0!");
  if(N == 0)
   return 0;
  int[] minSquare = new int[N + 1];
  int max = (int)Math.sqrt(N);
  for (int i = 0; i <= N; i++)
   minSquare[i] = i;
  for(int i = 1; i <= N; i++){
   for(int j = 1; j <= max; j++){
    if(i - j * j < 0)
     continue;
    minSquare[i] = Math.min(minSquare[i], minSquare[i - j * j] + 1);
   }
  }
  return minSquare[N];
 }

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

I was thinking about using recursion, then I had some problem dealing with extra zeros in cases such as n = 15...

So, I googled, and here comes my favorite Wikipedia:

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer n, is simply the multiplicity of the prime factor 5 in n!. This can be determined with this special case of de Polignac's formula:^[1]

where k must be chosen such that

and  denotes the floor function applied to a. For n = 0, 1, 2, ... this is

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, ... (sequence A027868 in OEIS).

For example, 5³ > 32, and therefore 32! = 263130836933693530167218012160000000 ends in

zeros. If n < 5, the inequality is satisfied by k = 0; in that case the sum is empty, giving the answer 0.

The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

It is as easy as you can imagine.

Math, ha!

Update: 2015 - 03 - 01

public int trailingZeroes(int n) {
       if (n < 5)
            return 0;
        int zeros = 0;
        int k = 1;
        while (n >= Math.pow(5, k)) {
            zeros += n / Math.pow(5, k);
            k++;
        }
        return zeros;
    }

The reason is that it looses precision after certain positions. The following code will not gives us the correct answer for very large n. Use the above code.

public class TrailingZeros {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int zeros = 0;
        int five = 5;
        while (n >= five) {
            zeros += n / five;
            five *= 5;
        }
        return zeros;
    }
}

Update: 2015 - 01 -15

I realize that the above code will exceed time limit, but I couldn't figure the reason.

public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        if (n == 5)
            return 1;
        int k = 0;
        while (Math.pow(5, k) <= n)
            k++;
        k--;
        int zeros = 0;
        while (k > 0) {
            zeros += n / Math.pow(5, k);
            k--;
        }
        return zeros;
    }