# 25.05.2023 [837. New 21 Game]

25.05.2023

837. New 21 Game medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/223

Problem TLDR

Probability sum of random numbers 1..maxPts sum be < n after it overflow k.

Intuition

For every event, we choose one number from numbers 1..maxPts. Probability of this event is p1 = 1/maxPts.

For example, n=6, k=1, maxpts=10: we can pick any numbers 1, 2, 3, 4, 5, 6 that are <=6. Numbers 7, 8, 9, 10 are excluded, because they are >6. After we pick one number with probability p1 = 1/10, the sum will be >=k so we stop. The final probability is the sum of individual valid choices p = sum(good_p1)

Another example, n=6, k=2, maxpts=10: our choices are

// n = 6, k = 2, maxpts = 10
// p_win1 1+1, 1+2, 1+3, 1+4, 1+5, 2,   3,  4,  5,  6
//        0.01 0.01 0.01 0.01 0.01 0.1 0.1 0.1 0.1 0.1 = 0.55

When we go to the second round in cases of 1+1, 1+2, 1+3, 1+4, 1+5, we multiply the probabilities, so p(1+1) = p1*p1.

Next, observe the pattern for other examples:

// n = 6, k = 3, maxpts = 10
// p_win  1+1+1, 1+1+2, 1+1+3, 1+1+4, 1+2, 1+3, 1+4, 1+5, 2+1, 2+2, 2+3, 2+4, 3,  4,  5,   6
//        0.001  0.001  0.001  0.001  0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.1 0.1 0.1 0.1
// sum=0.484


// n = 6, k = 4, maxpts = 10
// p_win  1+1+1+1 1+1+1+2 1+1+1+3 1+1+2 1+1+3 1+1+4 1+2+1 1+2+2 1+2+3 1+3  1+4  1+5  2+1+1 2+1+2 2+1+3 2+2  2+3  2+4  3+1  3+2  3+3  4   5   6
//         .0001   .0001   .0001   .001  .001  .001  .001  .001  .001  .01  .01  .01  .001  .001  .001  .01  .01  .01  .01  .01  .01  .1  .1  .1
//sum=0.3993

What we see is the sequence of 1+1+1+1, 1+1+1+2, 1+1+1+3, where we pick a number from 1..maxpts then calculate the sum and if the sum is still smaller than n we go deeper and make another choice from 1..maxpts.
That can be written as Depth-First Search algorithm:

fun dfs(currSum: Int): Double {
    ...
    var sumP = 0.0
    for (x in 1..maxPts)
    sumP += dfs(currSum + x)
    res = sumP * p1
}

This will work and gives us correct answers, but gives TLE for big numbers, as its time complexity is O(n2)O(n2).

Let’s observe this algorithm’s recurrent equation:
$$
f(x) = (f(x+1) + f(x+2)+…+f(x + maxPts))*p1
$$
$$
f(x + 1) = (f(x+2) + f(x+3) +…+f(x + maxPts)*p1 + f(x + 1 + maxPts))*p1
$$
subtract second sequence from the first:
$$
f(x) - f(x + 1) = f(x+1)*p1 - f(x+1+maxPts)*p1
$$
$$
f(x) = f(x+1) + (f(x+1) - f(x+1+maxPts))*p1
$$
This removes one dimension of iteration 1..maxPts. However, it fails the first case where currSum == k - 1, because the equation didn’t consider that not all x+maxPts are smaller than n. For this case, we must return (n-k+1)*p1 as we choose last number from range k - 1..n.

Approach

This problem is next to impossible to solve in an interview, given how many conclusions you must derive on the fly. So, hope no one will give it to you.

• use an array for the faster cache

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)

Code

fun new21Game(n: Int, k: Int, maxPts: Int): Double {
    // n = 6, k = 1, maxpts = 10
    // cards: 1 2 3 4 5 6 7 8 9 10
    // p_win1(6, 10) = count(1 2 3 4 5 6) / 10 = 0.6


    // n = 6, k = 2, maxpts = 10
    // p_win1 1+1, 1+2, 1+3, 1+4, 1+5, 2,   3,  4,  5,  6
    //        0.01 0.01 0.01 0.01 0.01 0.1 0.1 0.1 0.1 0.1 = 0.55


    // n = 6, k = 3, maxpts = 10
    // p_win  1+1+1, 1+1+2, 1+1+3, 1+1+4, 1+2, 1+3, 1+4, 1+5, 2+1, 2+2, 2+3, 2+4, 3,  4,  5,   6
    //        0.001  0.001  0.001  0.001  0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.1 0.1 0.1 0.1
    // sum=0.484


    // n = 6, k = 4, maxpts = 10
    // p_win  1+1+1+1 1+1+1+2 1+1+1+3 1+1+2 1+1+3 1+1+4 1+2+1 1+2+2 1+2+3 1+3  1+4  1+5  2+1+1 2+1+2 2+1+3 2+2  2+3  2+4  3+1  3+2  3+3  4   5   6
    //         .0001   .0001   .0001   .001  .001  .001  .001  .001  .001  .01  .01  .01  .001  .001  .001  .01  .01  .01  .01  .01  .01  .1  .1  .1
    //sum=0.3993
    val p1 = 1.0 / maxPts.toDouble()
    val cache = Array<Double>(n + 1) { -1.0 }
        // f(x) = (f(x+1) + f(x+2)+..+f(x + maxPts))*p1
        // f(x + 1) = (f(x+2) + f(x+3) +...+f(x + maxPts)*p1 + f(x + 1 + maxPts))*p1
        // f(x) - f(x + 1) = f(x+1)*p1 - f(x+1+maxPts)*p1
        // f(x) = f(x+1) + (f(x+1) - f(x+1+maxPts))*p1
    fun dfs(currSum: Int): Double {
        if (currSum == k - 1) return minOf(1.0, (n-k+1)*p1) // corner case
        if (currSum >= k) return if (currSum <= n) 1.0 else 0.0
        if (cache[currSum] != -1.0) return cache[currSum]
        //var sumP = 0.0
        //for (x in 1..minOf(maxPts, n - currSum)) {
             //    sumP += dfs(currSum + x)
        //}
        //val res = sumP * p1
        val res = dfs(currSum + 1) + (dfs(currSum + 1) - dfs(currSum + 1 + maxPts)) * p1
        cache[currSum] = res
        return res
    }
    return dfs(0)
}