คำอธิบายปัญหา
กำหนดลิสต์ nums ตัวเลขบวกไม่ซ้ำกัน หาจำนวน quadruple (a,b,c,d) ที่ต่างกันทั้งหมด และ a*b = c*d เรียงลำดับสำคัญ (a,b) และ (c,d) สลับได้
ตัวอย่าง
nums = [3, 6, 4, 8] → Output: 8
คู่ที่ให้ผลคูณ 24: (3,8) และ (4,6) → 8 แบบจัดเรียง
ขั้นตอนการแก้ปัญหา
- นับความถี่ของผลคูณทุกคู่
c[product] += 1 - สำหรับแต่ละผลคูณที่มี
xคู่: จำนวนวิธีเลือก 2 คู่ =x * (x-1) - แต่ละคู่จัดเรียงได้ 2 แบบ (a,b) และ (b,a) → คูณ 4
- ผลรวมทั้งหมด =
sum(x*(x-1) for x in c.values()) * 4
การตนการทำงาน (Python)
def solve(nums):
c = {}
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
x = nums[i] * nums[j]
c[x] = c.get(x, 0) + 1
ret = 0
for x in c.values():
ret += x * (x - 1)
return ret * 4
nums = [3, 6, 4, 8]
print(solve(nums)) # Output: 8
อินพุต / เอาต์พุต
Input: [3, 6, 4, 8] Output: 8
