5 Best Ways to Count Number of Fraction Pairs Whose Sum Equals 1 in Python

Rate this post

πŸ’‘ Problem Formulation: We want to create a program that takes a list of fractions and counts the number of unique pairs that sum up to 1. For instance, given the input fractions [1/3, 2/3, 1/2, 3/4, 1/4], the desired output is 2 since there are two pairs (1/3 and 2/3, 1/4 and 3/4) that sum up to 1.

Method 1: Using a Double Loop

This method involves iterating over the list of fractions with two nested loops, comparing each pair to see if they sum to 1. It’s a brute force approach but straightforward, as it doesn’t require additional data structures or algorithms.

Here’s an example:

from fractions import Fraction

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

fractions = [Fraction(1, 3), Fraction(2, 3), Fraction(1, 2), Fraction(3, 4), Fraction(1, 4)]
print(count_pairs(fractions))

Output:2

This code snippet defines a count_pairs function that takes a list of Fraction objects. It uses nested loops to compare every unique pair in the list and increments a counter if their sum is 1. The Fraction class from Python’s fractions module ensures accurate arithmetic with fractions.

Method 2: Using a Dictionary

The dictionary method utilizes a hash table to store the complements of each fraction (1 – fraction). It then checks for the existence of each fraction in the hash table, which allows for faster pairing than the previous method.

Here’s an example:

from fractions import Fraction

def count_pairs(fractions):
    count = 0
    complements = {1 - f for f in fractions}
    for f in fractions:
        if f in complements:
            count += 1
    return count // 2  # each pair is counted twice

fractions = [Fraction(1, 3), Fraction(2, 3), Fraction(1, 2), Fraction(3, 4), Fraction(1, 4)]
print(count_pairs(fractions))

Output:2

In this example, a set of complements is created by subtracting each Fraction from 1. The function then iterates over the original fractions, checking for each fraction in the complements set. Since each pair is counted twice, the final result is divided by 2.

Method 3: Using Sorting and Binary Search

This method involves sorting the list of fractions first and then using binary search to find the complement of each fraction. This reduces the time complexity of the pairing process as compared to the brute force double loop.

Here’s an example:

from fractions import Fraction
import bisect

def count_pairs(fractions):
    sorted_fractions = sorted(fractions)
    count = 0
    for i, f in enumerate(sorted_fractions):
        complement = 1 - f
        index = bisect.bisect_left(sorted_fractions, complement, i+1)
        if index < len(sorted_fractions) and sorted_fractions[index] == complement:
            count += 1
    return count

fractions = [Fraction(1, 3), Fraction(2, 3), Fraction(1, 2), Fraction(3, 4), Fraction(1, 4)]
print(count_pairs(fractions))

Output:2

After sorting the list of fractions, the code uses the bisect_left function from the bisect module to perform binary search for the complement of each fraction in the sorted list. Only pairs with a sum of 1 are counted, resulting in the desired total.

Method 4: Using a Set for One-Pass Hashing

This method iterates over the list only once, keeping track of seen fractions using a set for hashing and comparing each fraction with a potential complement that might already exist in the set.

Here’s an example:

from fractions import Fraction

def count_pairs(fractions):
    seen = set()
    count = 0
    for f in fractions:
        complement = 1 - f
        if complement in seen:
            count += 1
        else:
            seen.add(f)
    return count

fractions = [Fraction(1, 3), Fraction(2, 3), Fraction(1, 2), Fraction(3, 4), Fraction(1, 4)]
print(count_pairs(fractions))

Output:2

Each fraction is checked against the set of seen fractions for its complement. If found, the pair count is incremented, otherwise the fraction is added to the set. This one-pass approach can be more efficient than previous methods.

Bonus One-Liner Method 5: Using Comprehensions and Sets

This concise, one-liner method applies a set intersection to identify fraction pairs whose sum is 1, combining the concepts of complementing and set operations in a single expression.

Here’s an example:

from fractions import Fraction

fractions = [Fraction(1, 3), Fraction(2, 3), Fraction(1, 2), Fraction(3, 4), Fraction(1, 4)]
pair_count = len(set(fractions) & {1 - f for f in fractions}) // 2
print(pair_count)

Output:2

The code creates a set of the fractions and intersects it with a set comprehension that generates the complements. Dividing the length of the intersection by 2 yields the number of unique pairs, as each pair would have been counted twice.

Summary/Discussion

  • Method 1: Double Loop. Simple and easy to understand. Inefficient for large datasets due to its O(n^2) time complexity.
  • Method 2: Dictionary. Uses hashing for better performance. Efficient for moderately large datasets with O(n) time complexity.
  • Method 3: Sorting and Binary Search. Offers improved performance for large datasets. Time complexity is O(n log n) due to sorting.
  • Method 4: One-Pass Hashing with Set. Highly efficient for large datasets. The method also has O(n) time complexity but is slightly faster in practice than Method 2 since it requires only one pass over the data.
  • Method 5: Comprehensions and Sets. Extremely concise. Utilizes the efficiency of sets and comprehensions, but readability might be compromised for some developers.