หาจำนวนสมาชิกความต่างสูงสุดที่เพิ่มเข้าเซตได้ใน C++

ได้รับเซตของจำนวนเต็ม arr[n] งานคือหาจำนวนสมาชิกใหม่สูงสุดที่สามารถเพิ่มเข้าเซตได้ โดยสมาชิกใหม่ต้องเป็น "ความต่างสัมบูรณ์" |a - b| ของสมาชิกเดิม a, b ในเซต และต้องไม่ซ้ำกับสมาชิกเดิมและระหว่างกัน

นี่คือโจทย์คลาสสิก: ปิดเซตภายใต้การลบ (Closure under subtraction) ซึ่งนำไปสู่ ตัวคูณร่วมน้อยที่สุด (GCD) ของสมาชิกทั้งหมด

ทฤษฎีทางคณิตศาสตร์

ให้ g = gcd(สมาชิกทั้งหมดในเซต) และ M = max(เซต)

เซตที่ปิดภายใต้การลบจะกลายเป็น: {g, 2g, 3g, ..., M}

จำนวนสมาชิกสุดท้าย = M / g

จำนวนสมาชิกที่ **เพิ่ม** ได้ = M/g - n (n = จำนวนสมาชิกเดิม)

ตัวอย่าง

ตัวอย่างที่ 1

Input: set = {1, 5}

g = gcd(1,5) = 1, M = 5

เซตสุดท้าย: {1,2,3,4,5} (5 ตัว)

เพิ่มได้: 5 - 2 = 3 ตัว (คือ 2,3,4)

Output ต้นฉบับ: 1 ← ผิด (ควรเป็น 3)

ตัวอย่างที่ 2

Input: set = {2, 7, 1, 9}

g = gcd(2,7,1,9) = 1, M = 9

เซตสุดท้าย: {1,2,3,4,5,6,7,8,9} (9 ตัว)

เพิ่มได้: 9 - 4 = 5 ตัว

Output: 5 ✓

ตัวอย่างโค้ด (แก้ไข logic ให้ถูกต้อง)

#include <bits/stdc++.h>
using namespace std;

int maxAddableDifferences(vector<int> arr) {
    int n = arr.size();
    if (n == 0) return 0;
    
    int g = arr[0];
    int maxVal = arr[0];
    for (int x : arr) {
        g = gcd(g, x);
        maxVal = max(maxVal, x);
    }
    
    int finalSize = maxVal / g;
    return finalSize - n;
}

int main() {
    vector<int> arr1 = {1, 5};
    cout << "Addable: " << maxAddableDifferences(arr1) << endl;  // 3
    
    vector<int> arr2 = {2, 7, 1, 9};
    cout << "Addable: " << maxAddableDifferences(arr2) << endl;  // 5
    
    vector<int> arr3 = {6, 10, 14};  // g=2, M=14 → final={2,4,6,8,10,12,14} (7 ตัว)
    cout << "Addable: " << maxAddableDifferences(arr3) << endl;  // 7-3=4
    
    return 0;
}

ผลลัพธ์

Addable: 3
Addable: 5
Addable: 4

การพิสูจน์สรุป

1. การลบซ้ำๆ จะสร้าง g = gcd ของเซตได้ (Euclidean algorithm)
2. เมื่อมี g แล้ว สร้าง 2g, 3g, ... ได้โดยการบวกซ้ำ
3. ค่าสูงสุดไม่เกิน M (max เดิม) เพราะการลบให้ค่าน้อยลง การบวกต้องมาจากค่าที่มีอยู่
4. ดังนั้นเซตสุดท้าย = {g, 2g, ..., M} จำนวน M/g ตัว

หมายเหตุเกี่ยวกับโค้ดต้นฉบับ

โค้ดต้นฉบับคำนวณ total = temp / val และ max = total - size ซึ่งตรงกับทฤษฎีข้างต้น (temp=max, val=gcd) แต่ตัวอย่างที่ 1 ให้คำตอบ 1 ซึ่งผิด (ควรเป็น 3) น่าจากข้อผิดพลาดในการนับความต่างที่ "distinct and largest" แทนที่จะเป็น "ทั้งหมดที่เป็นไปได้"