Nim Game

Условие

Игра Ним начинается с нескольких кучек камней. В каждом ходе игрок может удалить любое количество камней (не менее одного) из одной кучи. Игрок, который не может сделать ход, проигрывает. Дано число n, представляющее общее количество камней. Определите, может ли первый игрок выиграть, если оба игрока будут действовать оптимально.

Примеры

Input: n = 4

Output: false

Explanation: Первый игрок может взять 1, 2 или 3 камня. Но вне зависимости от выбора, второй игрок всегда сможет взять оставшиеся камни и выиграть.

Input: n = 1

Output: true

Input: n = 2

Output: true

Решение

fun canWinNim(n: Int): Boolean {
    // Первый игрок выигрывает, если количество камней не кратно 4
    return n % 4 != 0
}

Временная сложность

O(1) — решение выполняется за постоянное время.

Пространственная сложность

O(1) — используется фиксированное количество памяти.