1409. Nim Game with Multiple Piles — Sprague-Grundy

In standard Nim, players alternately remove any positive number of stones from a single pile, and the player unable to move loses. Given the pile sizes with the first player to move, return the number of distinct winning first moves, where a winning move leads to a position from which the opponent cannot win. If the position is already losing for the first player, return 0.

Input: A JSON object {"piles": [<pile sizes>]}.

Output: Return the number of winning first moves.

Examples

Input: {"piles":[1,2,3]}
Output: 0
Explanation: The XOR is zero, so there are no winning moves -> 0.

Input: {"piles":[1,2,4]}
Output: 1
Explanation: Only pile 4 yields a XOR-zero position -> 1.

Constraints

• 1 <= len(piles) <= 10^5
• 0 <= piles[i] <= 10^9

Asked by