How can I reduce big O complexity of two for loops

The function must return the count of pairs of numbers in the array songs (integer array consisting of lengths of songs in seconds) such that the pairs formed add up to whole minutes.

long playlist(int songs_count, int *songs) {
    int i, j, k = 0;
    for (i = 0; i < songs_count; i++) {
        for (j = i + 1; j < songs_count; j++)
            if ((songs[i] + songs[j]) % 60 == 0)
                k++;
    }
    return k;
}

Solution

A first straight forward approach would be like this:

Create an array holding 60 entries with the remainder of seconds%60 initialized to all zeroes.
Calculate the remainder of each song and increment the related entry in the array.
Iterate over all possible remainders (1..29)
For each remainder you have a = array[i] songs and b = array[60-i] matching songs which you need to combine: num = a*b; k += num;
For i==0 and i==30 you need special handling as the matching song is in same array element: num = a*(a-1);

This will reduce the time complexity to O(N):

You need

a loop over n to populate the array (could be done once when building the song list) and
a loop over 0..30 for the calculation.

This results in O(N)+O(1)

Edit: Depending on your rules (does order of the songs matter) you might need to multiply with 2.