Bài toán mảng tổng (Sum Array Puzzle) trong C++

Mảng (Array) lưu trữ nhiều phần tử cùng kiểu, kích thước cố định.

Bài toán Sum Array: Cho mảng A kích thước n, tạo mảng S sao cho S[i] = tổng tất cả phần tử của A trừ A[i].

Ví dụ

A = {1, 2, 3, 4, 6} → S = {15, 14, 13, 12, 10}

Giải thích

• S[0] = 2+3+4+6 = 15
• S[1] = 1+3+4+6 = 14
• S[2] = 1+2+4+6 = 13
• S[3] = 1+2+3+6 = 12
• S[4] = 1+2+3+4 = 10

Thuật toán

Cách 1: O(n²) – Với mỗi i, cộng tất cả j ≠ i.

Cách 2: O(n) – Tính tổng toàn mảng trước

• Tính total = sum(A).
• S[i] = total - A[i].

Chương trình C++ mẫu (tối ưu O(n))

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

int main() {
    vector<int> arr = {3, 6, 4, 8, 9};
    int n = arr.size();
    
    long long total = 0;
    for (int x : arr) total += x;
    
    cout << "Mảng gốc: ";
    for (int x : arr) cout << x << " ";
    
    cout << "\nMảng tổng: ";
    for (int x : arr) cout << (total - x) << " ";
    return 0;
}

Kết quả

Mảng gốc: 3 6 4 8 9
Mảng tổng: 27 24 26 22 21