Challenge: Shortest Stretch Reaching a Target

Lab C++ Intermediate 20 points

Read 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 none.

Input

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

Output

One number.

Example

Input

6 7
2 3 1 2 4 3

Output

Sample input available Sample output available

Editor

C++

Hints

Grow the window with v[right].

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

Solution explanation

The window only moves forward: O(n).

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> v(n);
    for (auto& x : v) cin >> x;
    int left = 0, best = 0;
    long long total = 0;
    for (int right = 0; right < n; right++) {
        total += v[right];
        while (total >= target) {
            if (best == 0 || right - left + 1 < best) best = right - left + 1;
            total -= v[left++];
        }
    }
    cout << best << endl;
    return 0;
}

Output

Answer