Challenge: Shortest Stretch Reaching a Target

Lab Python Intermediate 20 points

Read a list of positive numbers and a target. Print the length of the shortest stretch of neighbouring numbers whose total is at least the target, or 0 if there is none.

Input

Line 1: positive whole numbers. Line 2: the target.

Output

One number.

Example

Input

2 3 1 2 4 3
7

Output

Sample input available Sample output available

Editor

Python

Hints

Grow the window by adding nums[right].

While the total is big enough, record the length and shrink from the left.

Solution explanation

The window only ever moves forward, so this is O(n).

Show solution

nums = list(map(int, input().split()))
target = int(input())
left = total = 0
best = 0
for right in range(len(nums)):
    total += nums[right]
    while total >= target:
        if best == 0 or right - left + 1 < best:
            best = right - left + 1
        total -= nums[left]
        left += 1
print(best)

Output

Answer