Track Pairs That Fill Whole Minutes

Medium

You are putting together a radio playlist. The length of each track in seconds is stored in the array durations. Tracks go on air in pairs, and the host likes a pair to run for an exact whole number of minutes. Count the pairs of tracks (i < j) for which durations[i] + durations[j] is divisible by 60. Checking every pair is O(n²); aim for O(n).

Example 1

durations=[45, 75, 15, 120, 105] → 4

The pairs 45+75=120, 45+15=60, 75+105=180 and 15+105=120 work, four in total. The 120 track is a whole number of minutes on its own, but has no partner.

Example 2

durations=[180, 240, 300, 360] → 6

All four tracks last a whole number of minutes, so any of the 6 pairs works.

Example 3

durations=[7, 11, 13] → 0

Constraints

1 ≤ len(durations) ≤ 6·10⁴
1 ≤ durations[i] ≤ 500

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Counting

Similar problems

More Than a Third of the Votes Medium Most Common Values Medium Jobs With a Cooldown Medium Most Searched Words Medium Domain Visit Rollup Medium

Input

durations=[45, 75, 15, 120, 105]

Expected

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