หาค่า k ที่ modulo กับทุกสมาชิกในอาร์เรย์ให้เหลือเท่ากันใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหาจำนวน k ทั้งหมดที่ทำให้ arr[i] % k ให้ผลลัพธ์เท่ากันสำหรับทุก i ในอาร์เรย์

ตัวอย่าง

Input: arr = {10, 4, 2}
Output: 1 2

หลักการคณิตศาสตร์

ถ้า x % k = y % k และ x > y ให้ d = x - y

x = y + d → x % k = (y + d) % k = y % k + d % k

ดังนั้น d % k = 0 → k ต้องเป็นตัวหารของ d

ขยายสู่อาร์เรย์: k ต้องเป็นตัวหารของผลต่างระหว่างค่าสูงสุดและต่ำสุด

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

1. เรียงลำดับอาร์เรย์
2. หาผลต่าง d = max - min
3. ถ้า d = 0 (ทุกค่าเท่ากัน) → k เป็นจำนวนใดๆ ก็ได้ (Infinite)
4. หาตัวหารทั้งหมดของ d
5. ตรวจสอบแต่ละตัวหารว่า arr[i] % k ให้ค่าเท่ากันทุก i หรือไม่

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

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

void findNumbers(int arr[], int n) {
    sort(arr, arr + n);
    int d = arr[n - 1] - arr[0];
    
    // ทุกค่าเท่ากัน
    if (d == 0) {
        cout << "Infinite number of k's";
        return;
    }
    
    // หาตัวหารของ d
    vector<int> divisors;
    for (int i = 1; i * i <= d; i++) {
        if (d % i == 0) {
            divisors.push_back(i);
            if (i != d / i) divisors.push_back(d / i);
        }
    }
    
    // ตรวจสอบแต่ละตัวหาร
    for (int i = 0; i < divisors.size(); i++) {
        int k = divisors[i];
        int temp = arr[0] % k;
        int j;
        for (j = 1; j < n; j++) {
            if (arr[j] % k != temp) break;
        }
        if (j == n) cout << k << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 4, 2};
    findNumbers(arr, 3);
    return 0;
}

ผลลัพธ์

1 2

ตรวจสอบ: 10%1=0, 4%1=0, 2%1=0 ✓ | 10%2=0, 4%2=0, 2%2=0 ✓

สรุป

ปัญหานี้ลดรูปเป็นการหาตัวหารร่วมของผลต่าง max-min แล้วตรวจสอบเงื่อนไข modulo หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ