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