BinarySearch 0825 Race to Finish Line

Problem statement

https://binarysearch.com/problems/Race-to-Finish-Line/

Solution

Equal to Leetcode 0818 Race Car, but we need to use more optimized approach: with more branches cut.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, target):
        q = deque([(0, 1, 0)])
        while q:
            d, s, pos = q.popleft()
            if pos == target: return d
            q.append((d + 1, s * 2, pos + s))
            if (s + pos - target) * s > 0:
                q.append((d + 1, -s//abs(s), pos))