Số phần tử chênh lệch tối đa có thể thêm vào tập hợp trong C++

Cho tập hợp (set) các số nguyên. Nhiệm vụ: tìm số lượng phần tử chênh lệch |a-b| khác nhau có thể thêm vào tập hợp, với a,b trong tập ban đầu.

Quan sát: Nếu d = GCD của tất cả phần tử trong tập, thì mọi chênh lệch |a-b| đều chia hết cho d. Tập hợp các chênh lệch có thể tạo ra chính là các bội số của d từ d đến (max - min).

Số lượng chênh lệch khác nhau = (max_val / d) - n, với n = số phần tử ban đầu.

Ví dụ 1

Input – set = {1, 5}

Output – 1

Giải thích: Chênh lệch: |1-5|=4. Chỉ có 1 giá trị.

Ví dụ 2

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

Output – 5

Giải thích: Các chênh lệch: 5,6,8,7,2. Có 5 giá trị khác nhau.

Thuật toán

1. Tìm GCD của tất cả phần tử (val).
2. Tìm phần tử lớn nhất (temp).
3. Tổng số bội số của val từ val đến temp: total = temp / val.
4. Kết quả = total - n (trừ đi n phần tử đã có).

Ví dụ code

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

int maxDiffElements(int arr[], int size) {
    int val = arr[0];
    int temp = arr[0];
    
    for (int i = 1; i < size; i++) {
        val = __gcd(val, arr[i]);
        temp = max(temp, arr[i]);
    }
    
    int total = temp / val;
    return total - size;
}

int main() {
    int arr[] = {2, 7, 1, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference elements: " << maxDiffElements(arr, size) << endl;
    return 0;
}

Kết quả

Maximum difference elements: 5

Lưu ý: Giải pháp này giả sử tập hợp đóng dưới phép lấy chênh lệch (tạo thành nhóm cyclic). Đúng khi tập ban đầu đã là tập các bội số của GCD.