Skip to content

464. Can I Win 👍

  • Time: $O(n \codt turns)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0)
      return true;

    const int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (sum < desiredTotal)
      return false;

    unordered_map<int, bool> mem;
    return canIWin(desiredTotal, 0, maxChoosableInteger, mem);
  }

 private:
  // Returns true if the first player can we, where `used` represents the used
  // numbers.
  bool canIWin(int total, int used, const int& maxChoosableInteger,
               unordered_map<int, bool>& mem) {
    if (total <= 0)
      return false;
    if (const auto it = mem.find(used); it != mem.cend())
      return it->second;

    for (int i = 1; i <= maxChoosableInteger; ++i) {
      if (used >> i & 1)  // Integer i is used.
        continue;
      if (!canIWin(total - i, used | 1 << i, maxChoosableInteger, mem))
        return true;
    }

    return mem[used] = false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 0)
      return true;

    final int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (sum < desiredTotal)
      return false;

    Map<Integer, Boolean> mem = new HashMap<>();
    return canIWin(desiredTotal, 0, maxChoosableInteger, mem);
  }

  // Returns true if the first player can we, where `used` represents the used
  // numbers.
  private boolean canIWin(int total, int used, int maxChoosableInteger, Map<Integer, Boolean> mem) {
    if (total <= 0)
      return false;
    if (mem.containsKey(used))
      return mem.get(used);

    for (int i = 1; i <= maxChoosableInteger; ++i) {
      if ((used >> i & 1) == 1) // Integer i is used.
        continue;
      if (!canIWin(total - i, used | 1 << i, maxChoosableInteger, mem))
        return true;
    }

    mem.put(used, false);
    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
    if desiredTotal <= 0:
      return True

    totalSum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
    if totalSum < desiredTotal:
      return False

    @functools.lru_cache(None)
    def dp(total: int, used: int) -> bool:
      """
      Returns true if the first player can we, where `used` represents the use
      numbers.
      """
      if total <= 0:
        return False
      return any((used >> i & 1) == 0
                 and not dp(total - i, used | 1 << i)
                 for i in range(1, maxChoosableInteger + 1))

    return dp(desiredTotal, 0)