Problem statement

https://binarysearch.com/problems/First-to-Count-to-Target/

Solution

We can use dp here. Or we can use game theory to prove that if target is divisible by k + 1, then answer is false: indeed, for every step x other player can make step k + 1 - x.

Complexity

It is O(1) here for time and space.

Code

class Solution:
    def solve(self, k, target):
        return target % (k + 1) != 0