Sort 316 Discussions, By:
Please Login in order to post a comment
unsigned long long int is not enough to store n^2 value for test cases 5 and 6. Therefore (at least in C) we need to use modular arithmetic. There is a multiplication rule, that says:
(ab)%n = ((a%n)*(b%n))%n
So in our case it's ((read_number%1000000007)^2)%1000000007
NO NEED to calculate every term, notice that Tn = 2n-1, thus Sn = 1 + 3 + 5 + ...+ 2n-1= (1+2n-1) * n / 2 = n*n.
My python solution
n = int(input())
You need not make it that complicated
t(n) = n^2 - (n-1)^2
See the pattern.
Every addition in S(n) we are subtracting the previous term
For better understanding see the inductive approach.
S1 = t1 = 1^2 - (n-1)^2 =1
S2 = t1 + t2 = 1 + 2^2 -(2-1)^2 = 1+4-1 = 4
S3 = S2 + t3 = 4 + 3^2 - (3-1)^2 = 4 + 9 - 4 = 9
So my answer would be
Sn = n^2%1000000007
Following the arithmatic progression
Sn = 1 + 3 + 5 + ...+ 2n-1= (1+2n-1) * n / 2 = n * n
So, the code in Python3
Tricky one. Just think about the series being computed. No need to compute items before n :)