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!
mequint2000 Gotta love it when your compiler has limitations...learned something new about modular math
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
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]
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)
khajenazaramani1 thanks alot dude it helped me alot
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
loco_poco 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.
trojan38f Why is this tagged medium? probably the easiest problem.
meriororen Try it in C :D
hiljusti Javascript also has some complexity too
mrasquinha Tricky one. Just think about the series being computed. No need to compute items before n :)
Whitecrash [deleted]
rupeshiya i cant understand how can be output for 5773408242017850 will be 112242846 ??????? whereas it should be n*n;
NagatoUzumaki 5773408242017850 % 1000000007 = 112242846
satyamsingh1601 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 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 For all those who are not able to solve the problem in some TestCases, use BigInteger. I hope it helps.
SaiSurya027 i am coding in c++ amd how to take that huge no. i passed all except two cases pls help me
ShubhamV06 even i am not getting in 2 test cases.pls help
SaiSurya027 What is your approach?
ShubhamV06 its okay! i got it! :D
byte10 not pass in 2 test cases..
q1a2z3 Use modular math after each step. (a*b)%m == ((a%m)*(b%m))%m
SaiSurya027 I got it.
pranavj1001 Cool
sakets594 how to use biginteger please answer
pranavj1001 You can go to this link to learn about how to use BigIntegers in Java
sakets594 dont we have biginteger in c/c++ thanx for link
pranavj1001 "long long" will do the job here, however there's this library also. Check it out ;)
anjithajose 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 The mod is 1000000007, not 1000000009.
anjithajose thank you so much
Sort 161 Discussions, By:
Please Login in order to post a comment