How can I reduce big O complexity of two for loops

Question

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;
}

Answer 1

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.

Answer 2

If the value of seconds is less, you can use hash map (unordered_map in c++) to solve it in ~O(n) complexity.

Suppose you know that the maximum value of the pair is 600 secs, then you can have another array storing these values.

for(int i = 1; i <= 10; i++)
{
    a[i-1] = i * 60;
}

//a[] = {60, 120, 180, 240, 300, 360, 420, 480, 540, 600};
unordered_map <int, int> mymap;

for(int i = 0; i < songs_count; i++)
{
    mymap[i] = songs[i];
}

Now you can modify your code as (Solution is for C++):

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

    //a[] = {60, 120, 180, 240, 300, 360, 420, 480, 540, 600};
    unordered_map <int, int> mymap;

    for(int i = 0; i < songs_count; i++)
    {
        mymap[i] = songs[i];
    }

    for (i = 0; i < songs_count; i++) 
    {
        for (j = 0; j < n /*size of a*/; j++)
        {
            if (a[j] > songs[i] && mymap.find(a[j] - songs[i]) != mymap.end())
            {
                k++;
            }
        }
    }
    return k;
}

Answer 3

You can bring down the complexity from O(N²) to O(N) with a simple approach:

• using an array int a[60], for each i in 0..59, compute the number of songs whose duration has i seconds and a whole number of minutes. A single pass is sufficient.
• for each i in the array, compute the number of pairs of songs of interest. again a single pass is needed.
• to compute the number of pairs, one needs extra specification:
  • are pairs ordered?
  • can a pair have twice the same song?

Assuming a pair must have different songs and order does not matter, here is an implementation:

long playlist(int songs_count, int *songs) {
    long a[60] = { 0 };
    int i;
    long total;
    for (i = 0; i < songs_count; i++)
        a[songs[i] % 60]++;
    total = (a[0] * (a[0] - 1) + a[30] * (a[30] - 1)) / 2;
    for (i = 1; i <= 29; i++)
        total += a[i] * a[60 - i];
    return total;
}

If order matters and pairs can have twice the same song, the computation is different:

long playlist(int songs_count, int *songs) {
    long a[60] = { 0 };
    int i;
    long total;
    for (i = 0; i < songs_count; i++)
        a[songs[i] % 60]++;
    total = 0;
    for (i = 0; i < 60; i++)
        total += a[i] * a[(60 - i) % 60];
    return total;
}