Why am I getting TLE in this code?

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll n, ll k){
if(k>n){
return gcd(n,k-n);
}
if(n>k){
return gcd(n-k,k);
}
if(n==k){
return k;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T;
cin >> T;
while(T–){
ll N,K;
cin >> N >> K;
cout << N/gcd(N,K)<< endl;
}
return 0;
}

Problem Code: MINPIZZAS

Hey @nazeefa_01 :wave: ,
Your logic is correct only issue is with your GCD implementation it is not optimal.I would recommend you to go through the link below it’ll help you.

https://cp-algorithms.com/algebra/euclid-algorithm.html

1 Like