# Summing the N series

# Summing the N series

Yksisarvinen + 21 comments 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

0timsmit0 + 1 comment This helped a lot, thanks!

isabelladom247 + 0 comments After reading the details that you are mentioned on the problem page the adding has become a very simple task. The details are explained perfectly will the addition of suitable examples photo editing services india. The program is the one I want but the details help me to understand the details perfectly.

mequint2000 + 1 comment Gotta love it when your compiler has limitations...learned something new about modular math

vishivhare2001 + 0 comments [deleted]

sachinxlr + 0 comments this helped, thank you

Seeker911 + 1 comment Yes u right. I still dont get the right answer in c# though. For input value 5773408242017850 I calculate 112242842 and should get 112242846. No idea why ??

Seeker911 + 1 comment Ok I was using a type Double and thats just going to cause trouble. Problem solved.

coder08122014 + 3 comments me too bro...i was using pow(n,2); ans same problem as yours now i am doing n*n and problem solved

bajpayee_kuntal + 1 comment can i ask what is the differece it makes with pow function or the n*n concept,how u come to know that u will get the least time by this process plss do help me man

1602038_PSTU + 1 comment If you have known somthing about Complexity analysis, the time complexity of pow(x,y) is

*O(n*, that means getting solution of single input you have about n^{2})^{2}ms. On the other hand, this method's time complexity is*O(1)*, that means getting solution of single input you have about only 1 ms .Melkon + 0 comments Time complexity is not about milliseconds. It would be ridicolous if multiplying 2 number woult take 1 ms. :)

n^2 simply means that for example:

- For input 10 the algorithm will be at worst case 10 * 10 =100 times slower.
- For an O(1) algorithm it takes approximately the same amount of time to calculate even if N = 1 or N = 10 billion.

But again, it has nothing to do with milliseconds or exact times, an O(1) algorithm could take 10 years too.

prernak7595 + 2 comments mine still not solved..

`long t; cin>>t; vector<int> arr(t); for(int arr_p=0;arr_p<t;arr_p++) { long n; cin>>n; cout<<n*n<<endl; }`

isn't this the answer? as cases 3 to 6 only are working.

GingFreecs + 0 comments [deleted]simondvt + 0 comments You are missing the modulo.

gk34961 + 0 comments **What you did actually int sum=(n*n); s.o.p(sum); will it pass all the test case??**

nishurishabh + 1 comment That was amazing bro. plz give the source.

q1a2z3 + 2 comments Well, this is one you can just think through. when you use the modulus function, you just repeatedly subtract the second number from the first:

9%2 == 9-2-2-2-2 == 9-2*4 == 1

Now, when you multiply two modulated (is that the correct word?) numbers, you can use the distributive property (foil method).

(9%2)*(7%2) == (9-2*4)*(7-2*3) == 9*7 + 9*(-2*3) + 7*(-2*4) + (-2*4)*(-2*3)

You'll notice that those last three terms are always going to be multiples of the modulator (I don't actually know math terms!). No matter what numbers you use, if you multiply (a%m)*(b%m), you will always end up with a*b + [some random numbers that will all be multiples of "m"]. If you modulate this final expression by "m", then those last numbers will all not matter, since they are perfect multiples of "m", and we can remove them. So...

( (a%m)*(b%m) )%m == (a*b)%m

Use that equation the other way around, and you can keep your numbers smaller by modulating (some math nerd out there is cringing) them early on, preventing overflow problems.

joycexu0122 + 1 comment Just one question, is it 9*7 + 9*(-2*3)+7*(-2*4)+(-2*4)*(-2*3). Thanks for your explanation!

q1a2z3 + 0 comments Oops, let me fix that. Thanks. You're right.

debneilsaharoy + 0 comments Thanks..this helped for test cases 5 and 6 while running in c++!!

tecknovice + 0 comments it helps a lot! thanks!

neerajkumar71971 + 0 comments thanks learnt really something good and new

hail_the_king + 0 comments Thanks, this helped!

joycexu0122 + 1 comment This helped a lot! Can anybody help me why mod 10^9+7? Thanks.

mat_jastrzebski + 0 comments it has a few properties that make it commonly used with challenges such as this one. It's prime, it fits 32 bit data type, and it's the first of 10-digit numbers to satisfy these two criteria. When doing modulo operations with it you are guaranteed never to exceed 64 bit data type and as such not to run into type overflow issues when computing big numbers. It's convenient but in terms of getting consistent results it doesn't matter what modulus is used , as long as it is prime.

There are many resources explaining this in more depth on the web such as this one: https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/

sankireddyvinee1 + 1 comment sn=1+3+5+7+.... which is equal to sum of odd term series.... s1=(1*1)-(0-0)=1; s2=(2*2)-(1*1)=3; s3=(3*3)-(2*2)=5; s4=(4*4)-(3*3)=7; from above s1,s2,s3,s4 equations we can see that first term of first equation(s1) and second term of second equation(s2) gets cancelled,simillarly first term of second equation(s2) and second term of thid equation(s3) gets cancelled..and so on... at last we remain with (4*4)-(0*0) i.e (n*n)-(0*0) i.e (n*n) therefore... sn=n*n; given in question that sn%(10^9+7) ->(n*n)%(10^9+7) we have a theorem which states that.. (a*b)%n=((a%n)*(b%n))%n ->(n*n)%(10^9+7) ->(n*n)%(1000000007) frm above theorem.. ->((n%1000000007)*(n%1000000007))%1000000007) the above theorem helps us to clear test case 5 & 6

mat_jastrzebski + 1 comment The expression

`((n%mod)*(n%mod))%mod`

is not really an application of the identity`(ab)%m = ((a%m)*(b%m))%m`

that you as well as the top post mentions since`n%mod*n%mod != n`

for`n>mod`

.If you wanted to use this identity, you would have to do it for

`a=sqrt(n)`

,`b=sqrt(n)`

-`((sqrt(n)%mod)*(sqrt(n)%mod))%mod`

, or any other`a`

and`b`

that satisfy the`a*b=n`

equation.The reason why it works here is due to the fact that for

`a*b=c`

,`c%mod = ((a%mod)*(b%mod))%mod`

and that's the property that should be referred to when applying`((n%1000000007)*(n%1000000007)%1000000007)`

expression.Note that for a non-prime integer

`n`

, there are some integers`a`

,`b`

for which`n=a*b`

is true but when`n`

is prime,`a=1`

and`b=n`

which doesn't simplify anything.All in all both identies look similar but there's a subtle difference worth knowing about that may save you some pain down the road.

jjlearman + 0 comments I disagree. Start with the identity:

(ab)%m = ((a%m)*(b%m))%m

Substitute n for a and n for b and you get:

(nn)%m = ((n%m)*(n%m))%m

This is exactly what we need, since we're trying to calculate (nn)%m, without exceeding the word length.

hotdudehvfun + 0 comments that really helped

vishwasjha17 + 0 comments thanks i do it like this:)

# include

# include

# include

# include

# include

# define m 1000000007

using namespace std;

int main() {

int t; cin>>t; while(t--) { unsigned long long int n; cin>>n; n=n%m; cout<<(n*n)%m< } /* Enter your code here. Read input from STDIN. Print output to STDOUT */

return 0; }NagatoUzumaki + 2 comments as we know, sum of n odd numbers = n^2

for _ in range(int(input())): n = int(input()) print((n ** 2) % 1000000007)

rauf_huseynov_77 + 0 comments [deleted]kirubha_16p119 + 0 comments awesome

khajenazaramani1 + 0 comments thanks alot dude it helped me alot

akhildua15 + 0 comments thanks

pedro_pfxr + 1 comment if you solve the equation manually you do not need n^2... (n-1)^2 expanded goes to n^2 -2n +1. So you have Tn= n^2 - (n^2 -2n +1) Tn= 2n-1

You do not need modular arithmetic!

Yksisarvinen + 0 comments Well, If you now sum all T_n up, it becomes n^2, which is beyond the limits of 64-bit unsinged integer. That's why modular arithmetic is needed.

16bce108 + 0 comments Thanks a lot! This was very helpful!

pythonban + 0 comments I python'ed' away every problem.

shivamsinghps + 0 comments [deleted]18H51A05D8 + 0 comments mathematical rule (n* n) -(n-1)* (n-1)=2* n -1

utkarshgupta2811 + 1 comment how is this expression is formed??

aish_vikas + 0 comments - ( n*n ) - ( n-1 ) ^ 2
- ( n^2 ) - ( (n^2) - (2*n) +1)
- ( n^2 ) - (n^2) + (2*n) -1
- //so n^2 will cancel and the remaining is the equation;

yli131 + 4 comments 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.

zac_c_petit + 1 comment For those wondering why,

T_n = n^2 - (n - 1)^2 = n^2 - ((n - 1)(n - 1)) = n^2 - (n^2 - 2n + 1) = 2n - 1

gkatsanos + 5 comments Okay, I get why

`T_n = 2n - 1`

, basic square expansion. But from that, how do you calculate`Î£_n`

?yli131 + 1 comment have no idea what you are trying to do...the result is n*n, that's all

gkatsanos + 1 comment I'm trying to understand where does this

`n*n`

comes from / how did you get there , connecting the dots from the fact that`T_n = 2n - 1`

till your resultgkatsanos + 2 comments thus Sn = 1 + 3 + 5 + ...+ 2n-1= (1+2n-1) * n / 2 = n*n.

that's what I don't get how do you reach to this

gkatsanos + 4 comments Thanks, I know what an arithmetic progression is but could you explain how do you get this

`(1+2n-1) * n / 2`

zac_c_petit + 0 comments If you understand arithmetic progression that result should not need further explanation. The link provided gives a proof of the arithmetic series, you should read it.

zac_c_petit + 2 comments But! If than answer isn't sufficient for you... proof by induction.

S_1 = 1 = 1^2 S_n = n^2 S_n+1 = n^2 + (n + 1)^2 - (n + 1 - 1)^2 = (n + 1)^2 - (n^2 - n^2) S_n+1 = (n + 1)^2

t_egginton + 0 comments very nice, i havent seen a proof by induction in ages!

Isdaril + 0 comments Yeah, I like this proof better too... The other one is just overcomplicating things

yli131 + 1 comment In this sequence, Sn = 1 + 3 + 5 + ...+ 2n-1, the first item is 1, the last item is (2n-1), there are altogether n items in the sequence. If you are asking how to sum all the items in an arithmetic progression, I can give you an example, 1+ 2 + ... + 100, you can see that 1+100 = 101, 2 + 99 = 101, 3 + 98 = 101, ... 49+ 52 = 101, 50 + 51 = 101, so you just need to pair the first and last item, and how many pairs are there? 50 pairs, so the sum is (1+100) * 100/ 2; I cannot think any more to explain this to you but I really think that link is sufficient enough

gkatsanos + 1 comment Thanks, I had forgotten there's a rule that the sum of a progression is always n*(firstelement+lastelement)/2 . Now things are clear.

bearhack + 0 comments It's actually defined as n(n+1)/2, because if the series has an odd number of elements, then the center element needs to be added in hence: summish(3) = 1 + 1 + 2 + 2 + 3 + 3 / 2 = (3)(3+1) / 2 = 12 / 2 = 6

akashbhadouria85 + 0 comments To find the sum of numbers in an airthmetic progression,you have a defined formula which can be proved. sum of progression = n/2*(1st term + last term); where n stands for total number of terms in that series.

ayushjain199999 + 0 comments Elementary mathematics... Î£n= n(n+1)/2 Î£1 = n

[deleted] + 0 comments use A P summation formula n/2(2a+(n-1)d)

aakash89qwerty + 0 comments sum of natural no is n*(n+1)/2 therefore that of 2n-1 is n(n+1)-1

aakash89qwerty + 0 comments [deleted]prernak7595 + 0 comments Î£n=(n)(n+1)/2 Î£(2n-1)=Î£(2n)-Î£(1) = 2Î£n- n= 2n(n+1)/2 -n =n*n

Bibliophage + 1 comment Isn't that a little overcomplicated?

S_n = (n^2 - (n-1)^2) + ((n-1)^2 - (n-2)^2) + ... + (1 - 0)

The only terms in this sum that don't cancel are the first and last: n^2 and 0.

Partial sums arrive at the same answer but I think the above logic is what the question is contructed around.

Isdaril + 0 comments Indeed :)

zeroshiiro + 0 comments Is there a need to calculate for T

_{n}= 2n-1? As far as I can see the sequence resolves to S_{n}= n^{2}as all the other terms cancel out and (n-1)^{2}for t_{1}is zero. Wouldn't this give constant time solution? Or am I missing something?sebinjude + 0 comments [deleted]

sebinjude + 2 comments My python solution

n = int(input()) print((n**2)%1000000007)

**Explanation**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

jjlearman + 1 comment The only reason this works in Python3 is that Python3 has unlimited length integers, and you're lucky that the input doesn't have a problem that takes too long in Python arithmetic.

Note that it would fail in Python2.

Your simplification is correct, though.

pgmreddy + 0 comments Not this comment, but I have seen some of your other comments, I guess you should do more math challenges, possible put yourself into 100 rank, best of luck.

shivamsinghps + 1 comment why modulo 10000007

pgmreddy + 0 comments Hope you meant 1000 000 007, it's a requirement given in the question https://www.hackerrank.com/challenges/summing-the-n-series/problem

This is to make sure the answer is not too big, especially in C++ & like.

For example, see this: https://www.hackerrank.com/contests/modular-operation/challenges/huge-factorial

It says: "Since result can be very large we want you to print result modulo (10^9 + 7)"

trojan38f + 3 comments Why is this tagged medium? probably the easiest problem.

meriororen + 1 comment Try it in C :D

hiljusti + 0 comments Javascript also has some complexity too

shubhamrangadal + 0 comments try in python3 by using just using for loop and formula,... then u will know y its tagged with medium

pgmreddy + 0 comments Guess top 100 rank is easy too. You should try. ~1700 to 100 is not very far.

shibaayanm + 1 comment Following the arithmatic progression Sn = 1 + 3 + 5 + ...+ 2n-1= (1+2n-1) * n / 2 = n * n So, the code in Python3

def summingSeries(n): return n**2%(10**9+7)

gromag + 1 comment Does yous pass @shibaayanm?

I have got exactly the same code however I get different results from the expected output.

For input

1

218194447

I get

953253555

but the expected result is:

218194447

Thanks

shibaayanm + 0 comments Yes I passed all the test cases. Can you please try once again? May be some points we're missing? All the best. Happy coding

Sort 252 Discussions, By:

Please Login in order to post a comment