โปรแกรมนับคู่เศษส่วนที่ผลรวมเท่ากับ 1 ใน Python

สมมติว่ามีรายการเศษส่วน แต่ละอันเป็นรายการ [numerator, denominator] แทนค่า numerator/denominator ต้องการหาจำนวนคู่ที่ผลรวมเท่ากับ 1

ตัวอย่าง: fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]] ผลลัพธ์คือ 4 คู่คือ (2/7 + 5/7), (3/12 + 3/4), (3/4 + 1/4), (4/14 + 5/7)

ขั้นตอนการแก้ปัญหา

1. สร้าง map d ว่าง, ans = 0
2. วนลูปแต่ละเศษส่วน i:
   • x = i[0], y = i[1]
   • ลดรูปด้วย g = gcd(x, y), x /= g, y /= g
   • คำนวณคู่ที่ต้องการ: temp_x = y - x, temp_y = y
   • ถ้า (temp_x, temp_y) อยู่ใน d: ans += d[(temp_x, temp_y)]
   • d[(x, y)] = d.get((x, y), 0) + 1
3. คืนค่า ans

ตัวอย่างโค้ด

class Solution:
    def solve(self, fractions):
        import math
        d = {}
        ans = 0
        for i in fractions:
            x = i[0]
            y = i[1]
            g = math.gcd(x, y)
            x /= g
            y /= g
            temp_x = y - x
            temp_y = y
            if (temp_x, temp_y) in d:
                ans += d[(temp_x, temp_y)]
            d[(x, y)] = d.get((x, y), 0) + 1
        return ans

ob = Solution()
fractions = [[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]
print(ob.solve(fractions))

อินพุต

[[2, 7], [3, 12], [4, 14], [5, 7], [3, 4], [1, 4]]

เอาต์พุต

4