464. Can I Win

In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise return false. Assume both players play optimally.

 

Example 1:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Example 2:

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3:

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

 

Constraints:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn can_i_win(max_choosable_integer: i32, desired_total: i32) -> bool {
        let nums: Vec<i32> = (1..=max_choosable_integer).collect();
        let n = nums.len();
        if desired_total > nums.iter().sum::<i32>() {
            return false;
        }
        let mut memo: HashMap<u32, bool> = HashMap::new();
        Self::dp(desired_total, (1 << n) - 1, &mut memo, &nums, n)
    }

    fn dp(total: i32, bitset: u32, memo: &mut HashMap<u32, bool>, nums: &[i32], n: usize) -> bool {
        if let Some(&res) = memo.get(&bitset) {
            return res;
        }
        let mut res = false;
        for i in 0..n {
            if res {
                break;
            }
            if 1 << i & bitset > 0 {
                if total - nums[i] <= 0 {
                    res = true;
                }
                res |= !Self::dp(total - nums[i], bitset & !(1 << i), memo, nums, n);
            }
        }
        memo.insert(bitset, res);
        res
    }
}
#[test]
fn test() {
    let max_choosable_integer = 10;
    let desired_total = 11;
    let res = false;
    assert_eq!(
        Solution::can_i_win(max_choosable_integer, desired_total),
        res
    );
    let max_choosable_integer = 4;
    let desired_total = 6;
    let res = true;
    assert_eq!(
        Solution::can_i_win(max_choosable_integer, desired_total),
        res
    );
    let max_choosable_integer = 5;
    let desired_total = 50;
    let res = false;
    assert_eq!(
        Solution::can_i_win(max_choosable_integer, desired_total),
        res
    );
    let max_choosable_integer = 18;
    let desired_total = 188;
    let res = false;
    assert_eq!(
        Solution::can_i_win(max_choosable_integer, desired_total),
        res
    );
}

Having problems with this solution? Click here to submit an issue on github.