Why am I getting a TLE?

general
1

Here’s the problem https://www.spoj.com/problems/LOCKER/
I have coded the following solution (using some hints from different sources):

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define mod 1000000007

int modpower(ll x, int y)
{
	x %= mod;
	if(!x) return 0;
	int res = 1;
	while(y)
	{
		if(y&1) res = (res*x)%mod;
		x = (x*x)%mod;
		y >>= 1;
	}
	return res;
}

int solve(ll n)
{
	if(n == 0) return 1;
	else if(n == 2) return 2;
	else if(n == 3) return 3;
	else
	{
		int rem = n%3;
		if(rem == 0) return modpower(3,n/3);
		else if(rem == 1) return 4*modpower(3,n/3 - 1);
		else return 2*modpower(3,n/3);
	}
}

int main()
{
	FASTIO
	int t;
	cin >> t;
	while(t--)
	{
		ll n;
		cin >> n;
		cout << solve(n) << "\n";
	}
	return 0;
}

Now I don’t know why I am getting a TLE. Please help.

2

Integer overflow…
Calling function modpower(x,y) where u have taken y as int type, as per constraints mentioned in the question , n can be up to 10^12 so u clearly need to declare it as long long so as to avoid overflow.
Declare int y and return type of function both as ll and when returning something like x*modpower(a,b) ,u should take modulo again and return it %mod

3 
#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define mod 1000000007

ll modpower(ll x, ll y)
{
	x %= mod;
	if(!x) return 0;
	ll res = 1;
	while(y)
	{
		if(y&1) res = (res*x)%mod;
		x = (x*x)%mod;
		y >>= 1;
	}
	return res;
}

ll solve(ll n)
{
	if(n == 0) return 1;
	else if(n == 2) return 2;
	else if(n == 3) return 3;
	else
	{
		int rem = n%3;
		if(rem == 0) return modpower(3,n/3);
		else if(rem == 1) return (4*modpower(3,n/3 - 1))%mod;
		else return (2*modpower(3,n/3))%mod;
	}
}

int main()
{
	FASTIO
	int t;
	cin >> t;
	while(t--)
	{
		ll n;
		cin >> n;
		cout << solve(n) << "\n";
	}
	return 0;
}

I have edited the code, but I still get TLE.

4

I tried recursive version of modular exponentiation keeping everything same and it got WA.
So check your logic once and speaking about your code’s time complexity , it is perfectly fine with the constraints so u may check your logic again.
Function i used
ll fpower(ll x,ll y)
{
if(!y)
return 1;
x = x%mod ;
return (y&1) ? x * fpower(x * x%mod,y/2)%mod : fpower(x * x%mod,y/2)%mod ;
}

1 Like
5

@say_ch_ee_zz Thanks for looking into the matter. I tried finding any flaw in the logic by using some sample cases, but I got correct answers for all of them. And I certainly could not find any piece in this code that might be the cause for a TLE. Maybe there is something that I am unable to spot out. Can anyone please help?

6

The first test case where your code fails is n=1
And it is also the cause for TLE

1 Like
7

Thanks @say_ch_ee_zz :smiley:

1 Like