 # Beginner Special 20 - Exam Time

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