Calculate the number of trailing zeroes in a sequence

Consider the sequence where s(0) and s(1) are inputs, and s(n) = s(n-1) * s(n-2) for all n >= 2. I want to find the number of trailing zeros in s(n). We can assume the following:

n, s(0), and s(1) are given as inputs
n <= 40
s(0) <= 20
s(1) <= 20

Below is my code attempt. It is not running when n is greater than 30 (it runs for a very long time). Is there any other way to calculate the number of trailing zeroes?

public class Soroco {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BigInteger n = new BigInteger(br.readLine());
    BigInteger s0 = new BigInteger(br.readLine());
    BigInteger s1 = new BigInteger(br.readLine());
    BigInteger num = s(n, s0, s1);
    System.out.println(num);
    System.out.println(countTrailingZeroes(num));
  }

  static BigInteger s(BigInteger n, BigInteger s0, BigInteger s1) {
    if (n.equals(new BigInteger("0")))
        return s0;
    else if (n.equals(new BigInteger("1")))
        return s1;
    else {
        BigInteger n1=n.subtract(new BigInteger("1"));
        BigInteger n2=n.subtract(new BigInteger("2"));
        BigInteger n3=s(n1, s0, s1).multiply(s(n2, s0, s1));
        return n3;
    }
  }

  static int countTrailingZeroes(BigInteger num) {
    String str = String.valueOf(num);
    int count = 0;
    for (int i = 0; i < str.length(); i++)
        if (str.charAt(i) == '0')
            count++;
    return count;
  }
}

Solution

Instead of performing the entire multiplication, you only need to keep track of the factors of 2 and 5. If a number can be written as N = 2^a * 5^b * (factors other than 2 or 5), then the number of trailing zeros in N is min(a, b). (This is because a trailing zero is just a factor of 10, which requires one 2 and one 5.)

Note that multiplication adds together the exponents of the factors. So, if you can write:

s(n-2) = 2^a * 5^b * (factors other than 2 or 5)
s(n-1) = 2^c * 5^d * (factors other than 2 or 5)

Then we have:

s(n) = s(n-1) * s(n-2)
     = 2^(a+c) * 5^(b+d) * (factors other than 2 or 5)

Therefore, we can treat this problem like two Fibonacci sequences. You start with the number of 2s and 5s in s(0) and s(1), and compute the number of 2s and 5s in s(2), s(3), ..., s(n) in the Fibonacci-sequence manner:

#2s in s(n) = (#2s in s(n-1)) + (#2s in s(n-2))
#5s in s(n) = (#5s in s(n-1)) + (#5s in s(n-2))

Finally, the number of trailing zeros is min(#2s in s(n), #5s in s(n)).

The above algorithm (if implemented with a loop, or memoized recursion) is O(n). Your attempt was exponential in n, which is why it takes a long time to run even for n = 30. I don't mean to bash your attempt, but it's good to understand these mistakes -- your code is slow for two main reasons:

First, multiplying very large integers with complete precision (as you're doing with BigInteger) is extremely slow, since the number of digits can double with each multiplication. If you only care about the number of trailing zeros, complete precision isn't necessary.

Second, ignoring the cost of multiplication, your recursive implementation of s is still exponential-time, but it doesn't have to be. Notice that you're computing the same values many times -- s(n-2) is computed separately for both s(n) and s(n-1), but the value of s(n-2) is clearly the same. The trick is to memoize the recursion by remembering previously-computed results, to avoid recomputation. Alternatively, you can compute Fibonacci-like sequences with a loop:

// Computes the n-th Fibonacci number in O(n) time
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
    fib[i] = fib[i-1] + fib[i-2];
return fib[n];

This is a much simpler approach than memoized recursion, at least for this problem.