[Java] [Задачи Spoj] Превышен лимит времени - Как сделать это быстрее? - PullRequest
Новая
       19

[Java] [Задачи Spoj] Превышен лимит времени - Как сделать это быстрее?

0 голосов
/ 15 сентября 2018

Моя проблема в том, что мой код отлично работает при выполнении в IDE, но он превышает ограничение по времени на Spoj.Я не получаю никаких подсказок о том, как сделать его более эффективным. Spoj challenge

Вот мой код: 

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]);
        }
    }
}

1 Ответ

0 голосов
/ 15 сентября 2018

Я думаю: возьмите 60 в качестве примера (это один из примеров ввода в связанных задачах ). Вы правы в предположении в своем коде, что для каждого числа от 1 до 60 вам нужно только учитывать, сколько раз оно делится на 5, так как всегда будет достаточно чисел, кратных 2, чтобы у вас было столько нулей. Итак, сколько чисел от 1 до 60 делится один раз на 5? Ответ: 60/5 = 12. Сколько из этих 12 делится на 5 еще раз? 12/5 = 2 (игнорировать любой остаток). Добавьте 12 и 2 (= 14), чтобы записать, что до сих пор мы знаем, что факториал 60 делится на 5 14 раз. И из тех 2, сколько делится в третий раз? 2/5 = 0. Как только мы достигли 0, мы закончили. Ответ был 14 (это согласуется с ответом в примере в ссылке).

Так что сделайте из этого алгоритма способ найти ответ. Я думаю, что это будет несколько быстрее, чем программа, которую вы опубликовали.

Может также оказаться, что вы можете найти не слишком сложную формулу для суммы, которую я вычисляю, чтобы вы могли полностью избежать зацикливания. И, может быть, вы можете найти вдохновение здесь: Геометрическая прогрессия .

...