Tổng phần tử theo chỉ số của hai mảng, tách chữ số vào mảng mới trong C++

Giới thiệu

Cho hai mảng, tính tổng các phần tử cùng chỉ số. Nếu tổng có nhiều chữ số, tách từng chữ số vào mảng kết quả. Xử lý phần dư của mảng dài hơn.

Ví dụ

arr1 = {1, 2, 32, 4, 5}

arr2 = {1, 52, 3}

Xử lý:

• i=0: 1+1=2 → [2]
• i=1: 2+52=54 → [5,4]
• i=2: 32+3=35 → [3,5]
• i=3: 4 (chỉ arr1) → [4]
• i=4: 5 (chỉ arr1) → [5]

Kết quả: [2, 5, 4, 3, 5, 4, 5]

Mã nguồn hoàn chỉnh

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

void pushDigits(int num, vector<int> &result) {
    if (num > 0) {
        pushDigits(num / 10, result);  // Đệ quy xử lý chữ số hàng cao trước
        result.push_back(num % 10);    // Thêm chữ số hàng đơn vị
    }
}

void printVector(vector<int> &result) {
    for (int i : result) {
        cout << i << " ";
    }
    cout << endl;
}

void addTwoArrayElements(vector<int> arr_one, vector<int> arr_two) {
    vector<int> result;
    int n = arr_one.size(), m = arr_two.size();
    int i = 0;
    
    // Xử lý phần chung (cả hai mảng đều có phần tử)
    while (i < n && i < m) {
        pushDigits(arr_one[i] + arr_two[i], result);
        i++;
    }
    
    // Xử lý phần dư của mảng 1
    while (i < n) {
        pushDigits(arr_one[i++], result);
    }
    
    // Xử lý phần dư của mảng 2
    while (i < m) {
        pushDigits(arr_two[i++], result);
    }
    
    printVector(result);
}

int main() {
    vector<int> arr_one = {1, 2, 32, 4, 5};
    vector<int> arr_two = {1, 52, 3};
    addTwoArrayElements(arr_one, arr_two);
    return 0;
}

Kết quả chạy chương trình

2 5 4 3 5 4 5

Giải thích hàm pushDigits

Sử dụng đệ quy để tách chữ số theo thứ tự từ hàng cao đến hàng thấp:

pushDigits(54):
  pushDigits(5):
    pushDigits(0) → return
    push 5
  push 4
Kết quả: [5, 4]

Phân tích độ phức tạp

• Thời gian: O(N + M + tổng số chữ số) - tuyến tính
• Không gian: O(tổng số chữ số) - lưu kết quả

Cải tiến: Xử lý số 0

Hàm pushDigits hiện tại không xử lý num = 0. Cần thêm:

void pushDigits(int num, vector<int> &result) {
    if (num == 0) {
        result.push_back(0);
        return;
    }
    // ... code cũ
}

Kết luận

Bài toán kết hợp cộng mảng, tách chữ số (digit extraction) và đệ quy. Kỹ thuật tách chữ số dùng đệ quy rất phổ biến trong xử lý số lớn.