Đếm các cặp khác nhau từ hai mảng có cùng tổng chữ số trong C++

Cho hai mảng số nguyên arr_1[] và arr_2[], nhiệm vụ là đếm số cặp khác nhau (distinct pairs) mà tổng chữ số của hai phần tử trong cặp bằng nhau. Mỗi cặp gồm một phần tử từ arr_1[] và một từ arr_2[].

Ví dụ

Input - arr_1[] = {1, 22, 42, 17}, arr_2[] = {1, 31, 6, 8} Output - count is 4

Giải thích - Có 4 cặp có cùng tổng chữ số: (1,1), (22,31), (42,6), (17,8).

Input - arr_1[] = {1, 22, 42, 17}, arr_2[] = {2, 78, 6, 18} Output - count is 1

Giải thích - Chỉ có cặp (42,6) có cùng tổng chữ số.

Input - arr_1[] = {1, 22, 42, 17}, arr_2[] = {2, 78, 16, 18} Output - count is 0

Phương pháp tiếp cận

• Tạo hàm tính tổng chữ số của một số
• Duyệt qua tất cả các cặp (i,j) từ hai mảng
• Nếu tổng chữ số bằng nhau, lưu cặp vào set để tránh trùng lặp (sắp xếp thứ tự trong cặp)
• Trả về kích thước set

Ví dụ code C++

#include <iostream>
#include <set>
using namespace std;

int sumdigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int paircount(int arr_1[], int arr_2[], int size1, int size2) {
    set<pair<int, int>> myset;
    for (int i = 0; i < size1; i++) {
        for (int j = 0; j < size2; j++) {
            if (sumdigits(arr_1[i]) == sumdigits(arr_2[j])) {
                if (arr_1[i] < arr_2[j])
                    myset.insert({arr_1[i], arr_2[j]});
                else
                    myset.insert({arr_2[j], arr_1[i]});
            }
        }
    }
    return myset.size();
}

int main() {
    int arr_1[] = {1, 22, 42, 17};
    int arr_2[] = {5, 31, 6, 8};
    int size1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size2 = sizeof(arr_2) / sizeof(arr_2[0]);
    cout << "count is " << paircount(arr_1, arr_2, size1, size2);
    return 0;
}

Kết quả

count is 3