mod(remainder should be always positive). You can check on any ide -8mod5 . It is giving -3 but actual answer should be 2
Anyone, please tell me why am I getting TLE for this code.
Use pow instead of ** for exponentiation in the loop and this question can be done without exponentiation also.
using namespace std;
const unsigned int M = 1000000007;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
l n ; cin >>n;
l sum=0;
for ( l i = 0 ; i < n ; i++ ){
l var; cin >> var ;
if ( var<0){
sum+=(var%M+M)%M;
}
else{
sum+=var%M;
}
sum= sum%M;
}
l q; cin >> q;
for ( l j=0 ; j <q; j++){
sum+=sum;
sum = sum%M;
cout << sum<<endl;
}
return 0 ;
}
just take care of modulo while taking input
We want to output the answer in modulo field of MOD 10^9+7. So any number outside that range shall correspond to one value in range [0, 10^9+6].
For some x, we want to find y such that x = y + c*MOD and y \in [0, 10^9+6]. It can be see that for each x, thereās a unique y and c. Youād need to read on modular arithmetic, here and here
My idea for bonus problem is that since range [L, R] would be something like suffix of a rotation of A + Rotations of array A repeated X times for some X \geq 0 + prefix of a rotation A. There can also be a case where [L, R] correspond to a subarray of a rotation of A.
The sum of middle part is fixed. We need to determine the rotation of A which covers position L and R. This is the tricky part. Something like divide and conquer is possible here. Itād take time proportional to the number of times the array size is doubled.
Since array length doubles after each operation, and we want to keep L and R in long long range, there cannot be more than 64 queries of first type. Letās call that Q_1
Hence, the solution would be working in something like O(Q_1) for each query of second type.
Keep thinking for the exact approach 
True
bro in case x=0 means no rotation then why multiply by 2 ans will wrong
Hello friend!! actually logically ans for negative sum doesnt make any sense at all.You have to blindly follow the logic for negative no. Hope that helps!!!
bro question tells us to find mod 10^9 + 7 hence for negative values we have to use that logic only. dont think about the ans if it is making any logic or not . u have to just use mod concept for negative no . Thatās it!!! XD
Can anyone tell why it is showing TLE, when I directly perform modulo 10^9 +7)?
Also, please help me by telling what is the most efficient way of doing it.
@kumer_codechef @taran_1407 @sarvdeep_mark @lotthbrok @ssrivastava990 @usernameharsh @achal123789
i am new to codechef and cp
i know the code for this because i saw others submission and also got correct ans while submitting but i want to know why are we doing this ?
sum = ((sum % MOD) + MOD) % MOD;
why do we need to % + % 1000000007
cant we just add the initial sum of the array and then again keep adding q times
sum=sum+sum;
and then at the end
cout<<abs(ans)%1000000007;
@nk20422 why is -8 mod 5 is equal to 2 why not -3 or 3(positive) wherein 8 mod 5 is equal to 3
please can someone please help me in clearing my doubt
thank you in advance
In c++ if you take modulo of a negative number you will get a negative result which is in sync with the mathematical way of doing modulo operation but for the purpose of the problem, we have to convert the mod result in the range [0,n-1]. We can do this either by initially adding a multiple of the divisor to the number such that the resultant sum will be positive and then take the mod but thatās not the efficient way as it will take more steps rather we use the above-mentioned way. Now taking your example of -8 mod 5, either you can add
(5*2 + (-8)) mod 5 = 2
the main problem here is you have to run few steps to find the least divisor multiple which will make the sum positive which in this case is 2.
now use the above method.
-8 mod 5 = -3
(-3 + 5 ) mod 5 = 2.
I hope I havenāt messed it up a lot but this is what I can come up with the simplest explanation
1 Like
My Solution
Summary
mod = 10**9 + 7
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
temp = list(map(int, input().split()))
total = sum(arr)
for _ in range(q):
total = total*2 % mod
print(total)
sum=sum % MOD;
sum=((sum % MOD) + MOD) % MOD;
here MOD=1000000007 , My code gives error when i use first statement but it works absolutely fine when i use second statement to compute modulo.
Let array be
-1 -2 -2
here sum = -5
but as they asked you to print the ans modulo some value x
then ans should strictly lie between
0 to x-1
so if you do ( negative val ) % x
it might give negative ans which does not lie in 0 to x-1 hence the invalid ans .
hence first we raise negative number to positive and then find modulo ans .
and in this case ans will be always positive
Even if you raise positive number by x its modulo value will not change
for eg
( 2 % 5 ) == 2
( 2 + 5 ) % 5 == 2
3 Likes
@sarvdeep_mark
thank you so much for replying
i understood we need to make the negative ans into positive since we cannot take modulo for negative values
but while making the negative into positive why cant we just use abs(-ans)
for example abs(-8) mod 5 = 3
and 3 comes within 0 to n-1(0 to 5 in above eg)
abs(-1000000008) % 1000000007
=1
here also mod ans will always be in between 0 to 1000000007-1
((-1000000008 % 1000000007) + 1000000007)% 1000000007
=1000000006
this ans is also in between 0 to 1000000007-1
why the second ans is acceptable and why not the first ans?
Can anyone find small mistake in my code??
its link isā¦thanks
https://www.codechef.com/viewsolution/46944328
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll mod=1000000007;
int n;
cin >> n;
ll a[n], sum=0;
for(int i=0; i<n; i++){
cin >> a[i];
sum+=(mod+a[i])%mod;
}
if(sum<0){
sum=-1*sum;
}
int x;
cin >> x;
for(int i=0; i<x; i++){
ll y;
cin >> y;
}
for(int i=0; i<x; i++){
sum = 2*sum; // Result may overflow, apply modulo here
cout << sum << endl;
}
}
You forgot to apply Modulo at mentioned line.
1 Like