In tất cả dãy số liên tiếp tổng bằng N C++

Cho số nguyên dương N, in tất cả dãy số tự nhiên liên tiếp có tổng bằng N.

Ví dụ

N = 15 → 1+2+3+4+5=15, 4+5+6=15, 7+8=15

N = 25 → 3+4+5+6+7=25, 12+13=25

Phương pháp 1: Lồng vòng lặp (O(N²))

Với mỗi start từ 1 đến N/2, cộng dồn đến khi sum ≥ N.

void printConsecutiveSum(int N) {
    for (int start = 1; start <= N/2; start++) {
        int sum = 0;
        for (int i = start; sum < N; i++) {
            sum += i;
            if (sum == N) {
                for (int j = start; j <= i; j++) cout << j << " ";
                cout << endl;
                break;
            }
        }
    }
}

Phương pháp 2: Cửa sổ trượt tối ưu (O(N))

Duy trì cửa sổ [start, end], mở rộng end khi sum < N, thu hẹp start khi sum > N.

void printConsecutiveSum(int N) {
    int start = 1, end = 1, sum = 1;
    while (start <= N/2) {
        if (sum < N) {
            end++; sum += end;
        } else if (sum > N) {
            sum -= start; start++;
        } else { // sum == N
            for (int i = start; i <= end; i++) cout << i << " ";
            cout << endl;
            sum -= start; start++;
        }
    }
}

Kết quả (N=25)

3 4 5 6 7
12 13

Công thức toán học: Dãy từ a đến b có tổng = (a+b)(b-a+1)/2 = N. Duyệt độ dài L = b-a+1, giải a = (2N/L - L + 1)/2 phải là nguyên dương.

Độ phức tạp: Cửa sổ trượt O(N) time, O(1) space. Tốt nhất cho N lớn.