Why Am I getting WA??

Question: CPERM Problem - CodeChef

My Solution: CodeChef: Practical coding for everyone

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.

If N equals 1 you output -1.

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

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

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

@wefgef I am still getting WA

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

@wefgef Thanks, I get it.

1 Like

@kay_kay Thanks, I get it.