Solution: Pairs of Songs With Total Durations Divisible by 60

Problem Statement

You are given a list of positive integer times, where times[i] represents the duration of i<sup>th</sup> song in seconds.

Return the number of unique song pairs for which their total duration in seconds is multiple of 60. In other words, find the number of indices i, j such that i < j with (times[i] + times[j]) % 60 == 0.

Examples

Example 1:

Input: times = [30, 20, 150, 100, 40, 110]
Expected Output: 3

.....

Like the course? Get enrolled and start learning!

Giang Pham

· 2 years ago

count += remainderFrequency[0] * (remainderFrequency[0] - 1) / 2;

Java arithmetic operators are executed left to right
Fail test case in leetcode: an array length of 60000 containing only 60.
Array: [60 60 60 60 60 60 60 ....] (60000 60s are in this input array)
remainderFrequency[0] * remainderFrequency[0] - 1 = 60000 * 59999 = 3599940000
3599940000 is larger than the largest integer value in Java causing overflow
Solution: casting one of the number to long to preserve precision and prevent integer overflow

count += (long)remainderFrequency[0] * (remainderFrequency[0] - 1) / 2;