Превышен лимит времени в упражнении hackerearth

Я пытаюсь решить это упражнение в HackerEarth. Но у меня ошибка срок превышен. Это код, который я написал:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TestClass {
    //gcd 
    public static long gcd(long num1, long num2) {
        if (num2 != 0) {
            return gcd(num2, num1 % num2);
        } else {
            return num1;
        }
    }

    public static void main(String args[] ) throws Exception {
        //BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // Reading input from STDIN
        while (T-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st1.nextToken());
            long b = Long.parseLong(st1.nextToken());
            long A = a/gcd(a,b);
            long B = b/gcd(a,b);
            System.out.printf("%d%1s%d%n",B,"",A);
        }
    }
}

Во-первых, вы не должны вычислять gcd(a,b) дважды. Теперь, как правило, это обычно оптимизируется для вас, но, возможно, эта оптимизация компилятора неактивна для онлайн-судьи.

amit 17.05.2022 15:29

Возможно, вам следует попробовать итеративную реализацию GCD, чтобы избежать вызовов функций. Также примите во внимание то, что отметил @amit (gcd вычисляется дважды для одних и тех же аргументов).

Michail Alexakis 17.05.2022 15:49

Кроме того, вы можете использовать int вместо long везде. Указанный диапазон ввода будет аккуратно помещаться в int.

k314159 17.05.2022 16:13

Но в любом случае большая часть времени фактически тратится на ввод-вывод, чем на фактические вычисления.

k314159 17.05.2022 16:14

Выполнение ввода-вывода и загрузка кода JVM/загрузки и т. д.

Stephen C 18.05.2022 01:39

Также обратите внимание, что javadoc для StreamTokenizer указывает «StringTokenizer — это устаревший класс, который сохранен по соображениям совместимости, хотя его использование — обескуражен в новом коде».

Stephen C 18.05.2022 01:42
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
6
52
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ваше решение немного медленное из-за плохой реализации. Я переписал ваше решение в лучшей реализации с той же логикой и временной сложностью, что и ваше решение, и получил Принятый, и ни один из тестовых случаев не превысил 0,8 секунды.

import java.util.*;
 
class TestClass {
    // Same gcd function but it's better code :)
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);   
    }
 
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();  // this way of reading input is faster alot.
        while(t-- > 0) {
            int a = s.nextInt();  
            int b = s.nextInt();  // No need to use long it's  just 1e9

            int tmp = gcd(a, b);  // It's better to save the value of the gcd(a, b) instead of calculate it twice. 

            int A = a/tmp;
            int B = b/tmp;
            System.out.println(B+" "+A);
        }
    }
}

Другие вопросы по теме