Is there a pythonic way to count the pairs that total up to whole minutes

Question

I'm trying to find pairs of songs with durations that add up to whole minutes. Example given song lengths [10, 50, 90, 30]. Calculate the total number of different pairs. I'm expecting a return of 2 since the first and second pair to 60 seconds and the third and fourth songs pair to 120. But I'm instead getting 1 pair.

def pair_with_target_sum(songs, k):
    n = len(songs)
    count = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            if songs[i] + songs[j] == k:
                count += 1
    return count

def main():
    print(pair_with_target_sum([10, 50, 90, 30], 60))
    print(pair_with_target_sum([30, 20, 150, 100, 40], 60))

main()

your "is a whole minute" check is the trick here -- are you familiar with the procedure to check if a number is divisible by another number? — anthony sottile, Jan 02 '20 at 19:45
You are testing for the sum being 60, not "to whole minutes". — Scott Hunter, Jan 02 '20 at 19:45
Do you mean `sum(1 for c in itertools.combinations(songs, 2) if sum(c) % k == 0)` ? — Andrej Kesely, Jan 02 '20 at 19:47
What answer would you expect to get for `[10, 50, 50]` and for `[20, 40, 20, 40]`? — Mad Physicist, Jan 02 '20 at 20:02

score 3 · Answer 1 · answered Jan 02 '20 at 19:50

3

There is different, and much simpler algorithm:

Create array with 60 buckets.
For each value in list run counts[value % k] += 1
Sum min(counts[n], counts[(n + k) % k]) (the weird calculation instead of just using k - n is to handle special case 0)

answered Jan 02 '20 at 19:50

Hauleth

22,873
4
61
112

Beat me to it. I was going to suggest a`Counter` and just multiplying out the bucket for `n` and `(k - n)` – Mad Physicist Jan 02 '20 at 19:56
@MadPhysicist I assumed that @Levia wanted to use each "song" only once, that is why `min` call instead of multiplication. If they want number of possible combinations then the multiplication will be solution. – Hauleth Jan 02 '20 at 20:05
That makes sense. – Mad Physicist Jan 02 '20 at 20:08

score 1 · Accepted Answer · edited Jan 02 '20 at 20:05

1

I'd use the itertools.combinations in conjunction with the modulo operator:

from itertools import combinations

def f(songs):
    count = 0
    for pair in combinations(songs, 2):
        if sum(pair) % 60 == 0:
            count += 1

    return count

edited Jan 02 '20 at 20:05

Levia

65
8

answered Jan 02 '20 at 19:51

Lord Elrond

13,430
7
40
80

1

The problem is that this one has `O(n^2)` complexity while it can be done in `O(n)`. – Hauleth Jan 03 '20 at 09:59

score 0 · Answer 3 · answered Nov 03 '20 at 17:47

You can make your code work correctly with only changing a line and deleting the k parameter from your function definiton like this:

    def pair_with_target_sum(songs):
    n = len(songs)
    count = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            if (songs[i] + songs[j]) % 60 == 0:
                count += 1
    return count

def main():
    print(pair_with_target_sum([10, 50, 90, 30]))
    print(pair_with_target_sum([30, 20, 150, 100, 40]))
    print(pair_with_target_sum([60, 60, 60]))

main()

This works correctly for me when I run the code with different inputs.

Is there a pythonic way to count the pairs that total up to whole minutes

3 Answers3