 1484

# PREREQUISITES:

Basic modular arithmetic

# PROBLEM:

You have to consider a sequence of numbers where the first element is X. And each element after it, is the sum of all the elements before it. And you need to output the sum of the first N elements of this sequence.

# EXPLANATION:

Let us look at the first few elements of this sequence:

The first element is X.
The second element is the sum of everything which came before it, which is just X.
The third element is sum of first two, which is X+X = 2X.
The fourth element is sum of first three, which is X+X+2X = 4X.
The fifth element is sum of first four, which is X+X+2X+4X = 8X.

We see a pattern emerging. From the third element onwards, the elements seem to keep doubling. But it’s not obvious why that’s the case.

So now, instead, let’s look directly at the sum of the first i elements:

The sum of the first element is X.
The sum of the first two elements is X+X = 2X.
The sum of the first three elements is X+X + 2X= 4X.
The sum of the first four elements is X+X+2X+4X= 8X.

Here, we again see a very similar pattern, but now, starting from the second sum itself, the sums are double the previous sum.
And this is easy to see why - suppose the sum of the first 5 elements is some Y. Then the 6th element is Y, by definition. So then the sum of the first 6 elements is 2.
So generalizing this, we see that the sums are just X, 2X, 2^2X, 2^3X, 2^4X, 2^5X, \ldots. In particular, the sum of the first N elements is just 2^{N-1}X.

So given X and N, we just have to output (2^{N-1}X) \mod 1000000007. Since there are a lot of testcases, and the powers of 2 are independent of X, we can compute 2^{i} \mod 1000000007 for all values of i from 0 to 10^6, and store them in an array.

And we use the fact that (AB) \mod C = ( (A \mod C) * (B \mod C) ) \mod C to use the precomputed values of the modulos of the powers and get the answer for each testcase in constant time after the precomputation.

# TIME COMPLEXITY:

Time complexity is O(N + T).

# SOLUTION:

Tester's Solution
``````mod = 10**9 + 7
for _ in range(int(input())):
n, x = map(int, input().split())
print((pow(2, n-1, mod)*x)%mod)
``````
Editorialist's Solution
``````#include <iostream>
using namespace std;

long long int testcases, Pow, n, x, MOD = 1000000007;

int main() {

cin>>testcases;

Pow=1;
for(int i=1;i<=1000000;i++)
Pow[i] = (Pow[i-1] * 2) % MOD;

while(testcases--)
{
cin>>n>>x;
cout<<(x * Pow[n-1]) % MOD << "\n";
}

return 0;
}
``````
2 Likes

mod = 10*9+7
Expression: ((pow(2,n-1,mod)x)%(mod)) vs ((((2
(n-1))%mod)*x)%mod)

What is the difference between the time complexity of these two function as I am getting TLE in second expression and the first one is working fine?

It’ll be better if you give the two submission links

#include
using namespace std;

int main(){

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

``````long long testcases, Pow, n, x, MOD = 1000000007;

cin>>testcases;

Pow=1;
for(int i=1;i<=1000000;i++)
Pow[i] = (Pow[i-1] * 2) % MOD;

while(testcases--)
{
cin>>n>>x;
cout<<(x * Pow[n-1]) % MOD << "\n";
}

return 0;
``````

}

code is not working
if we shift long long testcases, Pow, n, x, MOD = 1000000007; above then main function then it is working.
what is happening here…