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()3 Answers
There is different, and much simpler algorithm:
- Create array with 60 buckets.
- For each
valuein list runcounts[value % k] += 1 - Sum
min(counts[n], counts[(n + k) % k])(the weird calculation instead of just usingk - nis to handle special case0)
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 countYou 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.
