Temperatures From Their Changes

Medium

A weather station kept a daily temperature log, but the log itself is gone. Only the changes survived: changes[i] is how many degrees day i + 1 differed from day i. So the log held len(changes) + 1 integers. Every value in the log is known to have been between low and high, inclusive. How many different logs are possible? If none, return 0.

Example 1

changes=[2, -1, -3], low=0, high=4 → 1

If the first reading is t, the rest are t+2, t+1, t-2. All of them fit in [0, 4] only for t = 2: the log 2, 4, 3, 0.

Example 2

changes=[0, 0], low=-1, high=1 → 3

The temperature never moved, so any of the three values -1, 0, 1 works.

Example 3

changes=[5, 5], low=1, high=8 → 0

Constraints

1 ≤ len(changes) ≤ 10⁵
-10⁵ ≤ changes[i] ≤ 10⁵
-10⁵ ≤ low ≤ high ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Prefix Sum

Similar problems

Shortest Stretch to the Goal Medium Product of All the Others Medium Studios for Recording Sessions Medium Longest Run with a Given Sum Medium Batch of Segment Adjustments Medium

Input

changes=[2, -1, -3], low=0, high=4

Expected

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