Two potters, Asha and Bo, share a single kiln that currently holds a charge of N unfired tiles. They fire the kiln in alternating turns, with Asha always moving first. On a turn, the potter to move must choose a positive integer d that is a divisor of the current tile count N and strictly less than N, then remove exactly d tiles from the kiln for firing, leaving N - d tiles behind for the next turn. If the potter to move has no such divisor available (which happens only once the charge has been reduced to a single tile), that potter loses the round immediately and the other potter is declared the winner. Both potters play with perfect strategy, each trying to force the other into the losing position. Given the starting charge N, determine who wins.
A single line containing one integer N, the starting number of tiles in the kiln.
Print Asha if Asha wins with optimal play from both sides, or Bo if Bo wins.
Example 1
Input
1
Expected
Bo
Explanation
With N = 1 there is no positive divisor d < 1, so Asha has no legal move on her very first turn and loses immediately, making Bo the winner.
Example 2
Input
4
Expected
Asha
Explanation
Asha removes 1 tile (a divisor of 4), leaving 3 tiles. Bo's only option from 3 is to remove 1 tile (3 is prime), leaving 2. Asha then removes 1 tile, leaving 1, and Bo has no legal move and loses. Since 4 is even, Asha wins, matching the general parity rule.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →