พิมพ์ผลรวมของจำนวนติดต่อกันที่เท่ากับ N ใน C++

ปัญหา

ได้รับจำนวนเต็มบวก N พิมพ์ลำดับจำนวนติดต่อกัน (Consecutive Numbers) ทุกชุดที่ผลรวมเท่ากับ N เช่น N=15 → 1 2 3 4 5 และ 7 8

วิธีแก้ (Simple)

บวกลำดับติดต่อกันจาก 1 ถึง N/2 พิมพ์ชุดที่ผลรวม = N

ตัวอย่างโค้ด (Simple)

#include <iostream>
using namespace std;

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

int main() {
    int N = 25;
    cout << "Sequence of consecutive numbers that sum up to " << N << " are :\n";
    printConsequtiveSum(N);
    return 0;
}

ผลลัพธ์

3 4 5 6 7
12 13

วิธีแก้ที่เหมาะสมกว่า (Optimal - Sliding Window)

ใช้ Precomputed Sum Array หรือ Two Pointers (Sliding Window) ลด Complexity

ตัวอย่างโค้ด (Optimal)

#include <iostream>
using namespace std;

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

int main() {
    int N = 25;
    cout << "Sequence of consecutive numbers that sum up to " << N << " are:\n";
    printConsequtiveSum(N);
    return 0;
}

ผลลัพธ์

3 4 5 6 7
12 13

คำอธิบาย

Two Pointers / Sliding Window: ขยาย end เมื่อ sum < N, ย่อ start เมื่อ sum > N พบคำตอบเมื่อ sum == N

Complexity: O(N) ดีกว่า Simple O(N²)

N=25: 3+4+5+6+7=25 และ 12+13=25