893. Pile Duel
At a village fair, two players face several heaps of pebbles, piles[i] pebbles in heap i. They alternate turns, the first player moving first. On a turn the player chooses one non-empty heap and removes any positive number of pebbles from it, up to the whole heap. A player who has no legal move because every heap is empty loses the game.
Both players play optimally. Return true if the first player wins, otherwise return false. Heaps may start empty.
Example 1
- Input:
- piles = [3,4,5]
- Output:
- true
- Explanation:
3 xor 4 xor 5 = 2, which is non-zero; reducing the pile of 3 to 1 leaves 1 xor 4 xor 5 = 0, a losing position for the rival, so the first player wins.
Example 2
- Input:
- piles = [6,6]
- Output:
- false
- Explanation:
Two equal piles: whatever the first player removes, the second player copies on the other pile, so the first player loses.
Constraints
- 1 ≤ piles.length ≤ 105
- 0 ≤ piles[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)