# Summing the N series

# Summing the N series

Yksisarvinen + 14 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 + 0 comments This helped a lot, thanks!

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

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 + 2 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 + 0 comments 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

prernak7595 + 1 comment 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]

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 + 0 comments as we know, sum of n odd numbers = n^2

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

khajenazaramani1 + 0 comments thanks alot dude it helped me alot

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

loco_poco + 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 + 1 comment 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 + 0 comments 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.

trojan38f + 1 comment 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

mrasquinha + 1 comment Tricky one. Just think about the series being computed. No need to compute items before n :)

Whitecrash + 0 comments [deleted]

rupeshiya + 1 comment i cant understand how can be output for 5773408242017850 will be 112242846 ??????? whereas it should be n*n;

NagatoUzumaki + 0 comments 5773408242017850 % 1000000007 = 112242846

satyamsingh1601 + 0 comments using the BigInteger Class in java

Scanner in=new Scanner(System.in); int T=in.nextInt(); for(int i=0;i<T;i++){ BigInteger n=in.nextBigInteger(); System.out.println(n.multiply(n).mod(new BigInteger("1000000007")));

singhgursheesh12 + 0 comments C++ Solution passing all tests

# include

using namespace std;

int main()

{

unsigned long long int t,sn,n;

cin >> t;

for(int i=1;i<=t;i++)

{

cin >> n;

sn=(n%1000000007)*(n%1000000007)%1000000007;

cout << sn << endl;

}

}

pranavj1001 + 3 comments For all those who are not able to solve the problem in some TestCases, use BigInteger. I hope it helps.

SaiSurya027 + 1 comment i am coding in c++ amd how to take that huge no. i passed all except two cases pls help me

ShubhamV06 + 2 comments even i am not getting in 2 test cases.pls help

SaiSurya027 + 2 comments What is your approach?

ShubhamV06 + 0 comments its okay! i got it! :D

byte10 + 0 comments not pass in 2 test cases..

q1a2z3 + 0 comments Use modular math after each step. (a*b)%m == ((a%m)*(b%m))%m

SaiSurya027 + 1 comment I got it.

pranavj1001 + 0 comments Cool

sakets594 + 1 comment how to use biginteger please answer

pranavj1001 + 1 comment You can go to this link to learn about how to use BigIntegers in Java

sakets594 + 1 comment dont we have biginteger in c/c++ thanx for link

pranavj1001 + 0 comments "long long" will do the job here, however there's this library also. Check it out ;)

anjithajose + 1 comment int main() {

`int t,i; long long n[11]; scanf("%d",&t); for(i=0;i<t;i++) scanf("%lld",&n[i]); for(i=0;i<t;i++) printf("%lld\n",(((n[i]%1000000009)*(n[i]%1000000009))%1000000009)); return 0;`

} kindlt tell me what is wrong with my code?

phildonnia + 1 comment The mod is 1000000007, not 1000000009.

anjithajose + 0 comments thank you so much

Sort 161 Discussions, By:

Please Login in order to post a comment