292. Nim Game

leetcode easy

#csharp#easy#heap#leetcode#queue

Task

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.

Вы и ваш друг поочередно делаете ходы, и вы ходите первым.

Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.

Тот, кто убирает последний камень, становится победителем.

Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4

Output: false

Explanation: These are the possible outcomes:

1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.

2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.

3. You remove 3 stones. Your friend removes the last stone. Your friend wins.

In all outcomes, your friend wins.

C# solution

matched/original

public class Solution {
    public bool CanWinNim(int n) {
        return n % 4 != 0;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanWinNim(int n) {
        return n % 4 != 0;
    }
}

Java solution

matched/original

public class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

JavaScript solution

matched/original

class Solution {
    canWinNim(n) {
        return n % 4 !== 0;
    }
}

Python solution

matched/original

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

Go solution

matched/original

package main

func canWinNim(n int) bool {
    return n % 4 != 0
}

Explanation

Algorithm

Определите базовый случай:

Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

Анализ оставшихся камней:

Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

Выигрышная стратегия:

Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎