TLE in OJUMPS

general
,
1

hey i’m getting TLE in ojumps and i cannot find the problem in the code pls help . the question is

the code is…

inp = int(raw_input())
i = 1
y = 0 
p = 0
while y<=inp:
	if y==inp:
		print "yes"
		p = 1
		break
	y = y + i
	if i==3:
		i = 0
	i+=1
if p==0:
	print "no"

thank you :slight_smile:

2

The constraints on a (inp in your solution ) are a<= 1018

Your solution is of O(a) complexity. So, it will not pass the test cases in the time limit specified.

Try some other logic.

You can refer to the editorial : http://discuss.codechef.com/questions/42547/ojumps-editorial

If you still have any problem, comment below.

1 Like
3

you are unnecessarily making use of loop in the problem .Remember that a can be as large as 10^18,which can result in 10^18 operations if you use loop (since your time complexity is o(a),which is the reason for tle.

Instead a simple implentation like the foll with 0(1) complexity would suffice.

Psuedo Cde:

get input a

a=a%6;

if(a==0||a==3||a==1)

print(“Yes”)

else

print(“No”)

if you find my post helpful upvote and mark it as accepted answer.CHEERS HAPPY CODING :slight_smile:

1 Like
4

I think you are using brute force in solving the problems. yesterday i had answerd a question on your doubt regarding the prob:“PLZLYKME”,where you had used a similar brute force kind of approach. Dont always fall into brute force,there is always scope for optimizations at any level.“optimisation is a virtue of a good programmer”,So always try to better your approach (keeping in mind the time consraints as well) which will help you in the long run. CHEERS HAPPY CODING:)