หา 4 ตัวประกอบของ N ให้ผลคูณมากที่สุด ผลรวมเท่า N - วิธีที่ 2 (Python)

โจทย์เดียวกับบทความก่อนหน้า แต่วิธีแก้ต่างออกไป: ใช้ Hash Map เก็บผลรวมคู่ตัวประกอบ

ตัวอย่าง: N=60 → ตัวประกอบ: 1,2,3,4,5,6,10,12,15,20,30,60 → ผลคูณมากสุด = 50625 (15×15×15×15)

อัลกอริทึม O(d²) ใช้ Hash Map

1. หาตัวประกอบทั้งหมด v[]
2. วนคู่ (i,j) ใน v: ถ้า v[i]+v[j] < N → เก็บ sum=v[i]+v[j] ใน v1[] และ map1[sum] = (v[i], v[j])
3. วน v1: element = N - v1[i] ถ้า element ใน map → ได้ 2 คู่ที่รวมกันได้ N
4. คำนวณผลคูณ 4 ตัว = a×b×c×d หาค่าสูงสุด

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

from math import sqrt, ceil

def get_product(n):
    my_map = {}
    v = []
    v1 = []
    
    # หาตัวประกอบ
    for i in range(1, ceil(sqrt(n)) + 1):
        if n % i == 0:
            v.append(i)
            if i != n//i and i != 1:
                v.append(n//i)
    
    s = len(v)
    max_prod = -1
    map1 = [0] * (n + 5)
    
    # สร้างคู่และผลรวม
    for i in range(s):
        for j in range(i, s):
            if v[i] + v[j] < n:
                sm = v[i] + v[j]
                v1.append(sm)
                map1[sm] = [v[i], v[j]]
                my_map[sm] = 1
    
    # หาคู่ที่รวมกันได้ N
    for sm in v1:
        element = n - sm
        if element in my_map:
            a, b = map1[sm]
            c, d = map1[element]
            max_prod = max(a * b * c * d, max_prod)
    
    if max_prod == -1:
        print("Not Possible")
    else:
        print("Maximum product", max_prod)

get_product(60)  # Maximum product 50625

ผลลัพธ์

Maximum product 50625

สรุป: ลดจาก O(d³) เป็น O(d²) โดยแยกเป็น 2 คู่ที่ผลรวมเท่า N ใช้ hash map lookup O(1) เร็วกว่าวิธีลูป 3 ชั้น