Can somebody please tell why the code is showing wrong answer for this question.

This is my solution.

Can somebody please tell why the code is showing wrong answer for this question.

This is my solution.

multiply by mod inverse 2 instead of when you are dividing or instead ,take 2 power (n-1) %mod as the answer

2 Likes

Anyone want to throw light on why the solution is correct for even N?

I just thought the problem setter missed an easy case (because the example test case was also wrong) so I was able to get AC, but really is it only me?

I think for 4 it shud be 5.

2 Likes

It is not correct for even N.And the sample TC is correct

1 Like

The sample test case has answer 8 for N=4

For N=4, we can easily see the number of ways as 4\choose{4} + 4\choose{3} = 5

Edit: Actually now that I see, the problem and test cases have been changed to specify Odd n. At least when I solved the problem during the contest, that was not the case. Itâ€™s good that it has been rectified.

2 Likes

OK , I didnt knew that

1 Like

How will doing this affect differently from what i didâ€¦Please throw light.

Yes this way it worked but please help how was it different that what i did.

You cannot divide a number once you are in modulo space.

Let me explain with an example.

Say 2^{3} \equiv 1 \mod 7

You can not say 2^{2} \equiv 1/2 \mod 7 (itâ€™s easy to see with this example).

Once you are in modulo space, you can still multiply, but for division, you need to multiply with inverse.

1 Like

The answer for general N is \sum\limits_{i=1+\lfloor\frac{N}{2}\rfloor }^{N} {N \choose i}. This sum comes out to be 2^{N-1} - \frac{1 + (-1)^N}{4}*{N \choose \lfloor\frac{N}{2}\rfloor }

4 Likes

refer cubercoder answer for thisâ€¦ )

Yeah but because of the mistake I couldnâ€™t solve it.

Yeah thanks appreciated

i also think that