Tìm số chia hết cho nhiều phần tử nhất trong mảng C++

Cho mảng, tìm phần tử trong mảng mà **chia hết cho nhiều phần tử khác nhất** (tính cả chính nó). Ví dụ: {4,24,16,3,12,28} → 4 chia hết cho 4,24,16,12,28? Thực ra 4 chia hết cho 4, 24 chia hết cho 4, 16 chia hết cho 4, 12 chia hết cho 4, 28 chia hết cho 4 → 4 chia 5 phần tử (kể chính nó). Kết quả 4.

Phương pháp: Vét cạn O(n²)

• Với mỗi i, đếm số j sao cho arr[i] % arr[j] == 0.
• Ghi nhớ i có count lớn nhất.

Ví dụ mã nguồn

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

int maxDivisibleCount(int arr[], int n) {
    int bestCount = -1, bestVal = -1;
    for (int i=0;i bestCount) {
            bestCount = cnt;
            bestVal = arr[i];
        }
    }
    return bestVal; // hoặc trả về bestCount
}

int main() {
    int arr[] = {4,24,16,3,12,28};
    cout << maxDivisibleCount(arr, 6); // 4
    return 0;
}

Kết quả

4

Số 4 là ước của 5 phần tử trong mảng.