# Summing the N series

# Summing the N series

Yksisarvinen + 15 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 + 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 + 0 comments 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 .

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.

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

khajenazaramani1 + 0 comments thanks alot dude it helped me alot

akhildua15 + 0 comments thanks

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

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

Whitecrash + 0 comments [deleted]

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")));

swimclan + 0 comments Unless someone can explain otherwise, you basically can't do these exercises in JS. The integer range is too big. Can't pass all cases. Here is my code:

var input = `10\n229137999\n344936985\n681519110\n494844394\n767088309\n307062702\n306074554\n555026606\n4762607\n231677104`; function processData(input) { //Enter your code here var lines = input.split('\n'); let T = parseInt(lines.shift()); lines.map(function(item) { return parseInt(item); }) .forEach(function(n) { console.log(Math.pow(n,2) % (Math.pow(10,9)+7)); }); } processData(input);

shibaayanm + 0 comments 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)

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

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;

}

}

Sort 167 Discussions, By:

Please Login in order to post a comment