1010. Pairs of Songs With Total Durations Divisible by 60

brute force: O(n^2)
find all pair, the %60 == 0 , count++

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int count = 0;
        for (int i = 0; i < time.length; i++) {
            for (int j = i + 1; j < time.length; j++) {
                if ((time[i] + time[j]) % 60 == 0 ) {
                    count++;
                }
            }
        }
        return count;
    }
}

T: O(n)

S: O(n)

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        Map<Integer, Integer> map  = new HashMap<>(); // mod value, count
        int count = 0;
        for (int t : time) {
            int timeValue = t%60;
            
            count += map.getOrDefault((60 - timeValue)%60, 0); // for exception: %60 (in t = 60, for 0~59 value, so do this)
            map.put(timeValue, map.getOrDefault(timeValue, 0)+1); // tricky
        }
        return count;
    }
}

/*




T: O(n)
use hashmap
and (60 - t%60)%60

reason for (60 - t % 60) % 60 expression: 
If the map already has 30, we need to look for the number 
is having remainder or not, this can be achieved with 60 - t%60. 
Eg, if the number is 210. 60 - 210 % 60 returns 30. 
30 is already in the list this can be paired up to form (30,210).

Reason for an extra % 60 over (60 - t % 60). 
if the t = 60, the expression 60 - t % 60 returns 60. 
this is beyond our remainers range (0,59)for 60. 
to make it with in the range in the case of 60 and multiples of 60, 
we are ufing an extra %60 on top of (60 - t % 60). 
this makes the remainder 0. which is with in the range of remainders for 60(0,59)


why map value also should %60?
record in HashMap in range : [0~59], or there are too many values in our map



Suppose we have [30, 150, 90].
Now, we will update map[150 % 60] = map[30] by 1, making our map contain 30: 2. 
What this means is that the next item that requires 30, will be able to make two pairs, one with 30, and one with 150.

Finally, we go to 90, and we are looking for 60 - 90 % 60 = 30. We see map[30] = 2,
=> so map[30] ++ , ans. = 3


if one more data 150 => [30, 150, 90, 150]

when last 150 => 
3            3
count += map.getOrDefault((60 - t%60)%60, 0);

=> ans = 6
*/