CODEWITHSUNDEEP
javatimelimit
kazaia
kazaia

Reputation: 3

[Java][Spoj challenges] Time Limit Exceeds - How to make it faster?

My problem is that my code works perfectly when executed on an IDE But it exceeds the the time limit on Spoj. I am not getting any hint on how to make it more efficient.Spoj challenge

Here is my code : 

import java.util.Scanner;

public class Factorial {

    public static int getDecomposition(int a) {
        int count = 0;
        int result = a;
        while (result % 5 == 0) {
            result /= 5;
            count++;
        }
        return count;
    }

    public static void main(String[] args) throws Exception {

        Scanner scan = new Scanner(System.in);
        int testCases = scan.nextInt();
        int sum[] = new int[testCases];
        int nums[] = new int[testCases];
        for (int i = 0; i < testCases; i++) {
            nums[i] = scan.nextInt();
        }
        for (int i = 0; i < testCases; i++) {
            for (int j = 5; j <= nums[i]; j = j + 5) {
                sum[i] += getDecomposition(j);
            }
            System.out.println(sum[i]);
        }
    }
}

Upvotes: 0

Views: 81

Answers (1)

Anonymous
Anonymous

Reputation: 86296

I’m thinking: Take 60 as an example (this is one of the example inputs in the linked challenges). You are correct in the assumption in your code that for each number from 1 to 60 you only need to consider how many times it’s divisible by 5, since there will always be enough numbers divisible by 2 that you will have this many zeroes. So how many of the numbers from 1 through 60 are divisible once by 5? Answer: 60 / 5 = 12. Out of those 12, how many are divisible by 5 once more? 12 / 5 = 2 (ignore any remainder). Add the 12 and the 2 (= 14) to record that until now we know that the factorial of 60 is divisible by 5 14 times. And out of those 2, how many are divisible a third time? 2 / 5 = 0. Once we’ve reached 0, we’re done. The answer was 14 (this agrees with the answer in the example in the link).

So make an algorithm out of this way of finding the answer. I think it will be somewhat faster than the program you have posted.

It may also be that you can find a not too complicated formula for the sum I am calculating so you can avoid looping altogether. And maybe you can find some inspiration here: Geometric progression.

Upvotes: 1

Related Questions