Sum Times Length Under a Limit

Hard

You are given an array of positive integers loads and a number limit. Define the weight of a stretch (a contiguous piece of the array) as the sum of its elements multiplied by its length. For example, the weight of [2, 5, 1] is (2 + 5 + 1) · 3 = 24. Count the non-empty stretches whose weight is **strictly less** than limit.

Example 1

loads=[3, 1, 2, 6], limit=8 → 5

The light stretches are [3], [1], [2], [6] and [1, 2], whose weight is (1 + 2) · 2 = 6. [3, 1] weighs 8, which is not below the limit.

Example 2

loads=[2, 2], limit=3 → 2

Each single 2 weighs 2. The pair weighs (2 + 2) · 2 = 8.

Example 3

loads=[5, 4, 1], limit=100 → 6

Constraints

1 ≤ len(loads) ≤ 10⁵
1 ≤ loads[i] ≤ 10⁵
1 ≤ limit ≤ 10¹⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Prefix Sum Sliding Window

Similar problems

Shortest Stretch Reaching a Total Hard Berry Walk Along a Path Hard Longest Affordable Run of Machines Hard Signal in the Remotest Village Hard Most Equal Values on a Budget Hard

Input

loads=[3, 1, 2, 6], limit=8

Expected

Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.