โปรแกรม C++ หาค่า k ที่ mod กับทุกสมาชิกอาร์เรย์ได้เหลือเท่ากัน

หาจำนวนเต็ม k ที่ modulus กับทุกสมาชิกในอาร์เรย์ได้เศษเหมือนกัน

ตัวอย่าง: arr = {12, 22, 32} → k = 1, 2, 5, 10

หลักการ: ถ้า x > y และ (y+d)%k = y%k → d%k = 0 ดังนั้น k ต้องเป็นตัวหารของความต่างระหว่างค่าสูงสุดและต่ำสุด ตรวจสอบตัวหารทุกตัวว่าให้เศษเท่ากันทุกสมาชิกหรือไม่

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

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

int equal_modulus(int arr[], int len) {
    sort(arr, arr + len);
    int diff = arr[len-1] - arr[0];
    vector<int> divi;
    for (int i = 1; i*i <= diff; i++) {
        if (diff % i == 0) {
            divi.push_back(i);
            if (i != diff/i) divi.push_back(diff/i);
        }
    }
    for (int i = 0; i < divi.size(); i++) {
        int temp = arr[0] % divi[i];
        int j;
        for (j = 1; j < len; j++)
            if (arr[j] % divi[i] != temp) break;
        if (j == len) cout << divi[i] << " ";
    }
    return 0;
}

int main() {
    int arr[] = {12, 22, 32};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout << "The values of K :" << endl;
    equal_modulus(arr, len);
    return 0;
}

ผลลัพธ์

The values of K : 1 2 10 5