Winner Take All (Solution)
In this blog, we will look at how you could approach the problem “Winner Take All” in The Coding Culture’s December Contest “Number Quest”.
Approach:
Following are the 3 cases that occur in problem for the given integer N :
Case #1: N is odd -
Since you begin the game, you can divide N by itself so that N/N = 1., and the Grinch loses.
Case #2: N is even and has no odd divisors greater than 1 -
Hence N is in the form of 2x. Since there are no odd divisors greater than 1, you are forced to subtract 1 from N. Since, (N-1) is odd, the Grinch can divide (N-1) by itself giving the result 1. Hence the Grinch would win the game.
Case #3: N is even but has odd divisors -
If N is divisible by 4, then you can divide N by its largest odd factor after which N becomes of the form 2x where x > 1. Hence, in this case, you win the game.
Case #4: N is even, has odd divisors and is in the form of 2*p -
Here p is odd. If p is prime, you can either subtract 1 or divide N by p, both of which would result in you losing the game. If p is not prime, then N is in the form p1.p2 where p1 is prime and p2 is odd. You can win the game by dividing N by p2.
