Why Am I getting WA??

general
,
1

Question: https://www.codechef.com/problems/CPERM

My Solution: https://www.codechef.com/viewsolution/12147288

I know that the solution to this problem is (2^(N-1) - 2) and I also know that the efficient way to find powers of 2 is by bitwise shift operator but I don’t know y i am getting WA.

Here is the code:

#include <iostream>
using namespace std;

int main() {
// your code goes here
int T,N;
cin>>T;
while(T--)
{
    cin>>N;
    long long int ans = (1<<(N-1))-2;
    cout<<ans<<"\n";
 }
 return 0;
   }

Please can anyone find the mistake in my code.

2

If N equals 1 you output -1.

3

@don_corleone_1 for n=1, output should be 0.

4

@wefgef I am still getting WA

5

Sorry, I just read the limits. The problem is that N <= 10^9, but integers can only hold 32 (or 64) bits. So when you compute 1 << N, if N > 31 your result effectively becomes 0. Try it out on your machine to convince yourself.

You should implement your own exponentiation function that also takes into account the fact that the result should be printed modulo 10^9+7.

1 Like
6

Notice the constraints:

1 <= N <= 10^9

So, many large powers cannot be stored in any datatype.
Ex: The largest possible ans will be (2^((10^9) - 1) - 2), which is not possible to store in any datatype. Hence you have to use Fast Exponential.

This below function will calculate (2^exp)%(10^9 + 7) efficiently.

LL fast_exp(LL exp) 
{
LL res = 1;
LL base = 2;
while(exp)
{
    if(exp%2 == 1)
        res = (res*base)%MOD;
    base = (base*base)%MOD;
    exp /= 2;
}
return res%MOD;
}

My Solution to that Question

1 Like
7

By using your method ,you can not calculate 2^N for N>=64 correctly due to Integer overflow.

The long long int data type is of 64 bits therefore it will give correct answer for N<64
but in the above problem
the constraints are very large for N.

The value of N can be : (1 ≤ N ≤ 10^9).

So, to solve this problem you have to apply Modular Exponentiation method.
The detailed tutorial on it is available here.

For further reference you can see my Solution.

1 Like
8

@wefgef Thanks, I get it.

1 Like
9

@kay_kay Thanks, I get it.