Home > Enterprise >  Time limit exceeded in hackerearth exercise
Time limit exceeded in hackerearth exercise

Time:05-17

I'm trying to solve this exercise in HackerEarth : https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/tin-and-creatures-2f60b404/ But I have an error of time limit exceeded. This is the code that I wrote :

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

Somebody can help me ?

CodePudding user response:

Your solution is a little bit slow because of the bad implementation. I rewrote your solution in better implementation with the same logic and time complexity of your solution and get Accepted and none of the test cases exceeded .8 second

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);
        }
    }
}
  • Related