BinarySearch 0649 Append Numbers to List to Create Range

Problem statement

https://binarysearch.com/problems/Append-Numbers-to-List-to-Create-Range/

Solution

Equal to Leetcode 0330. Patching Array.

Complexity

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

Code

class Solution:
    def solve(self, nums, n):
        reach, ans, idx = 0, 0, 0
        
        while reach < n:
            if idx < len(nums) and nums[idx] <= reach + 1:
                reach += nums[idx]
                idx += 1
            else:
                ans += 1
                reach = 2*reach + 1       
                
        return ans