I have been practicing Python on CodeChef I come up with the solution but some how it gave me error of Time Limit Exceeded. other code that gives same answer works fine which was submitted by other codechef members. My question is whats the difference between these two solutions.
My Code
t = int(input())
for _ in range(t):
n = int(input())
summ = 0
count = 0
for i in range(1, n+1):
summ +=i
count +=1
if summ%2==0:
print(n)
else:
print(n-1)
code submitted by other member of CodeChef
t = int(input())
for _ in range(t):
n = int(input())
sumN = (n*(n+1))//2
if sumN%2==0:print(n)
else:print(n-1)
>Solution :
In your code, you calculate the sum iteratively by adding each number from 1 to n, which requires n iterations.
In the other member’s code, they use the formula (n * (n + 1) /2 ) to directly calculate the sum in constant time, without the need for a loop.
The time complexity of your code is O(n) because the loop runs n times, performing addition and increment operations in each iteration. As a result, for large values of n, it can take a considerable amount of time to calculate the sum and determine the result.
On the other hand, the other member’s code has a time complexity of O(1) because the sum is calculated using a formula that doesn’t depend on the size of n. This allows their code to provide the result more efficiently.