Tìm N số nguyên duy nhất tổng bằng 0 trong C++

Cho số nguyên n, trả về mảng n số nguyên duy nhất (unique) có tổng bằng 0.

Thuật toán

1. Tạo mảng kết quả kích thước n
2. Gán n-1 phần tử đầu: 1, 2, 3, ..., n-1
3. Tính tổng x = 1+2+...+(n-1) = n(n-1)/2
4. Phần tử cuối = -x (để tổng bằng 0)

Tất cả phần tử đều khác nhau vì n-1 phần tử đầu dương khác nhau, phần tử cuối âm.

Ví dụ

n = 5 → {1, 2, 3, 4, -10} (tổng = 10 - 10 = 0)

n = 10 → {1, 2, 3, 4, 5, 6, 7, 8, 9, -45}

Chương trình mẫu

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << (i+1<v.size() ? ", " : "");
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> sumZero(int n) {
        vector<int> ans(n);
        int x = 0;
        for (int i = 0; i < n - 1; i++) {
            ans[i] = i + 1;
            x += i + 1;
        }
        ans[n - 1] = -x;
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.sumZero(10));
    return 0;
}

Kết quả

[1, 2, 3, 4, 5, 6, 7, 8, 9, -45]

Độ phức tạp: O(n) thời gian, O(n) không gian. Giải pháp đơn giản, luôn đúng với mọi n ≥ 1.

Lưu ý: Với n=1 → kết quả {0}. Với n=2 → {1, -1}.