4

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;
  }
}
mavericktz
  • 53
  • 6

2 Answers2

4

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.

k_ssb
  • 6,024
  • 23
  • 47
  • how to count number of 2's and number of 5's of a number – mavericktz May 27 '18 at 07:03
  • Simpler method would be to convert the number to a string and then check for the required number. If not you can go the hard way by dividing number by 10 everytime, and checking the remainder. If the remainder is your required number, good.. – Sparker0i May 27 '18 at 07:34
  • @mavericktz You can repeatedly divide by 2 or 5, until the number isn't divisible anymore. `int num2 = 0; while (n % 2 == 0) { n /= 2; num2++; }` – k_ssb May 27 '18 at 13:30
  • 1
    @Sparker0i We're talking about the number of 2s or 5s in the prime factorization. What you're suggesting would give the number of trailing 2s or 5s, which is completely different. – k_ssb May 27 '18 at 13:34
  • @pkpnd thanx, got the solution. – mavericktz May 27 '18 at 18:31
1
public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());

    int s0 = Integer.parseInt(br.readLine());

    int s1 = Integer.parseInt(br.readLine());

    int num21 = findNumberOf2s(s0);

    int num22 = findNumberOf2s(s1);

    int num51 = findNumberOf5s(s0);

    int num52 = findNumberOf5s(s1);

    int arr2[] = new int[n + 1];
    arr2[0] = num21;
    arr2[1] = num22;
    for (int i = 2; i <= n; i++)
        arr2[i] = arr2[i - 1] + arr2[i - 2];

    int arr5[] = new int[n + 1];
    arr5[0] = num51;
    arr5[1] = num52;
    for (int i = 2; i <= n; i++)
        arr5[i] = arr5[i - 1] + arr5[i - 2];

    System.out.println(Math.min(arr2[n], arr5[n]));

}

static int findNumberOf2s(int num) {
    int num2 = 0;
    while (num % 2 == 0) {
        num = num / 2;
        num2++;
    }
    return num2;
}

static int findNumberOf5s(int num) {
    int num5 = 0;
    while (num % 5 == 0) {
        num = num / 5;
        num5++;
    }
    return num5;
}
mavericktz
  • 53
  • 6