dsa · hard

Backlog Overtakes

Stations report readings, a list of integers. A reading at an earlier index **overtakes** a later one when it is strictly more than **twice** the later reading. Count all overtaking pairs (i, j) with i < j and readings[i] > 2 * readings[j], and return the count.

Arguments

Example

readings = [1,3,2,3,1]

Check each earlier index: 1 overtakes nothing. 3 (index 1) overtakes 1 (index 4) since 3 > 2. 2 (index 2) overtakes nothing (2 > 2 is false). 3 (index 3) overtakes 1 (index 4). Answer 2.

readings = [2,4,3,5,1] → 4 overtakes 1; 3 overtakes 1; 5 overtakes 1; also 4 overtakes... only 1. Answer 3.

Constraints

1 <= readings.length <= 10^5 -2 * 10^9 <= readings[i] <= 2 * 10^9 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[1,3,2,3,1]

Expected:
2

Example 2

Input:
[2,4,3,5,1]

Expected:
3

Example 3

Input:
[5]

Expected:
0

Open in the Dojo editor