หาตัวหารร่วมของทุกตัวยกเว้น 1 ตัวในอาร์เรย์ Python

ภาพรวม

โจทย์หาตัวเลข B ที่เป็นตัวหารของทุกสมาชิกในอาร์เรย์ ยกเว้นเพียง 1 ตัวเท่านั้น (GCD ของ n-1 ตัว)

ตัวอย่าง

อินพุต: [8, 16, 4, 24]

GCD ของ [8,16,24] = 8 (ไม่หาร 4 ลงตัว) → 8

อัลกอริทึม Prefix/Suffix GCD

1. สร้าง prefix_gcd[i] = GCD(arr[0..i])
2. สร้าง suffix_gcd[i] = GCD(arr[i..n-1])
3. สำหรับแต่ละ i คำนวณ GCD ของทุกตัวยกเว้น i:
   • i=0: suffix_gcd[1]
   • i=n-1: prefix_gcd[n-2]
   • อื่นๆ: gcd(prefix_gcd[i-1], suffix_gcd[i+1])
4. ถ้า arr[i] % cur != 0 → cur คือคำตอบ

โค้ด Python

from math import gcd

def getDivisor(array):
    n = len(array)
    if n == 1:
        return array[0] + 1
    prefix = [0] * n
    suffix = [0] * n
    prefix[0] = array[0]
    for i in range(1, n):
        prefix[i] = gcd(array[i], prefix[i-1])
    suffix[n-1] = array[n-1]
    for i in range(n-2, -1, -1):
        suffix[i] = gcd(suffix[i+1], array[i])
    for i in range(n):
        if i == 0:
            cur = suffix[1]
        elif i == n-1:
            cur = prefix[n-2]
        else:
            cur = gcd(prefix[i-1], suffix[i+1])
        if array[i] % cur != 0:
            return cur
    return 0

array = [8, 16, 4, 24]
print(getDivisor(array))

ความซับซ้อน

• เวลา: O(n log max_val)
• พื้นที่: O(n)

ผลลัพธ์

8