Yksisarvinen 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 This helped a lot, thanks!
isabelladom247 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 Gotta love it when your compiler has limitations...learned something new about modular math
vishivhare2001 [deleted]
sachinxlr this helped, thank you
Seeker911 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 Ok I was using a type Double and thats just going to cause trouble. Problem solved.
coder08122014 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 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 If you have known somthing about Complexity analysis, the time complexity of pow(x,y) is O(n2) , that means getting solution of single input you have about n2 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 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 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 [deleted]
simondvt You are missing the modulo.
gk34961 What you did actually int sum=(n*n); s.o.p(sum); will it pass all the test case??
nishurishabh That was amazing bro. plz give the source.
q1a2z3 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 Just one question, is it 9*7 + 9*(-2*3)+7*(-2*4)+(-2*4)*(-2*3). Thanks for your explanation!
q1a2z3 Oops, let me fix that. Thanks. You're right.
debneilsaharoy Thanks..this helped for test cases 5 and 6 while running in c++!!
tecknovice it helps a lot! thanks!
neerajkumar71971 thanks learnt really something good and new
hail_the_king Thanks, this helped!
joycexu0122 This helped a lot! Can anybody help me why mod 10^9+7? Thanks.
mat_jastrzebski 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 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 The expression
((n%mod)*(n%mod))%modis not really an application of the identity(ab)%m = ((a%m)*(b%m))%mthat you as well as the top post mentions sincen%mod*n%mod != nforn>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 otheraandbthat satisfy thea*b=nequation.The reason why it works here is due to the fact that for
a*b=c,c%mod = ((a%mod)*(b%mod))%modand 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 integersa,bfor whichn=a*bis true but whennis prime,a=1andb=nwhich 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 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 that really helped
vishwasjha17 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 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 [deleted]
kirubha_16p119 awesome
khajenazaramani1 thanks alot dude it helped me alot
akhildua15 thanks
pedro_pfxr 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 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 Thanks a lot! This was very helpful!
pythonban I python'ed' away every problem.
shivamsinghps [deleted]18H51A05D8 mathematical rule (n* n) -(n-1)* (n-1)=2* n -1
utkarshgupta2811 how is this expression is formed??
aish_vikas - ( 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 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 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 Okay, I get why
T_n = 2n - 1, basic square expansion. But from that, how do you calculateΣ_n?yli131 have no idea what you are trying to do...the result is n*n, that's all
gkatsanos I'm trying to understand where does this
n*ncomes from / how did you get there , connecting the dots from the fact thatT_n = 2n - 1till your resultgkatsanos 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 Thanks, I know what an arithmetic progression is but could you explain how do you get this
(1+2n-1) * n / 2zac_c_petit 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 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 very nice, i havent seen a proof by induction in ages!
Isdaril Yeah, I like this proof better too... The other one is just overcomplicating things
yli131 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 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 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 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 Elementary mathematics... Σn= n(n+1)/2 Σ1 = n
[deleted] use A P summation formula n/2(2a+(n-1)d)
aakash89qwerty sum of natural no is n*(n+1)/2 therefore that of 2n-1 is n(n+1)-1
aakash89qwerty [deleted]prernak7595 Σn=(n)(n+1)/2 Σ(2n-1)=Σ(2n)-Σ(1) = 2Σn- n= 2n(n+1)/2 -n =n*n
Bibliophage 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 Indeed :)
zeroshiiro Is there a need to calculate for Tn = 2n-1? As far as I can see the sequence resolves to Sn = n2 as all the other terms cancel out and (n-1)2 for t1 is zero. Wouldn't this give constant time solution? Or am I missing something?
sebinjude [deleted]
sebinjude 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 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 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 why modulo 10000007
pgmreddy 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 Why is this tagged medium? probably the easiest problem.
meriororen Try it in C :D
hiljusti Javascript also has some complexity too
shubhamrangadal try in python3 by using just using for loop and formula,... then u will know y its tagged with medium
pgmreddy Guess top 100 rank is easy too. You should try. ~1700 to 100 is not very far.
shibaayanm 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 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 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