CODEWITHSUNDEEP
javapythonalgorithmtime-complexity
mn0
mn0

Reputation: 31

Counting efficiently all the pairs with given sum

I came across the following question.

Given a list where each item represents the duration expressed in seconds of a song, return the total number of pairs of songs such their durations sum to minutes (e.g., 1m0s, 2m0s,..)

Example:
Input: [10,50,20,110,40]
Output: 3 (considering pairs at indexes (0,1),(0,3),(2,4))

I can only think to a brute force approach where I consider all pairs of songs. The time complexity of this approach is O(n^2).
Is there any better way of doing it?

Upvotes: 0

Views: 1175

Answers (2)

prashant
prashant

Reputation: 348

Think on the lines of hashing, creating buckets and modulo division. All the possible minutes will go into one of 60 possible buckets. Then think how many possible combinations can there be when you choose two of second values from any two buckets. Then use nC2 to count. Here's my solution in Java.

public int numPairsDivisibleBy60(int[] time) {
    int k = 60;
    int[] mods = new int[k];
    for (int i = 0; i < time.length; i++) 
        mods[time[i] % k]++;
    // n(n-1)/2 pairs for multiples of k and numbers which leave remainder as half multiple of k
    int count = ((mods[0] * (mods[0] - 1)) / 2) +
                ((mods[k / 2] * (mods[k / 2] - 1)) / 2);
    for (int i = 1; i < k / 2; i++)
        count += mods[i] * mods[k - i];
    return count;
}

Upvotes: 0

Nilesh
Nilesh

Reputation: 1343

  1. The given problem can be reduced to the fact that we need to discover pairs (a,b) such that (a + b) mod 60 == 0 from the given list A.
  2. Observation #1: For any integer x, (x mod 60) lies from o to 59.

  3. Initialise an array of length 60 with default value set to 0 the index i of which will store the number of elements in the list A, such that x mod 60 = i for all x belonging to A

    int freq[60] = {0};
for(int i = 0; i < A.size(); i++)
  freq[(A[i] % 60)]++;

  4. Now iterate over the array A again and for for every x, we need the count for the index 60 - (x mod 60) from our cumulative frequency map, which will corresponds to the number of elements it can form a pair with. The case where (x mod 60) == 30 would be a tricky one, which will require us to subtract 1 from the frequency count.

    int ans = 0;
for(int i = 0; i < A.size(); i++) {
  ans += freq[60 - (A[i] % 60)];
  if(A[i] % 60 == 30) ans--;
}

The overall complexity of the solution is O(n).

Upvotes: 1

Related Questions