โปรแกรมนับจำนวนรายการติดต่อกันที่ผลรวมเท่ากับ n ใน C++

เราได้รับตัวเลข n เป้าหมายคือหาจำนวนลำดับ (lists) ของจำนวนเต็มบวกที่ติดต่อกัน (consecutive) ที่ผลรวมเท่ากับ n

ตัวอย่าง: n = 15 → 4 ลำดับ: [1,2,3,4,5], [4,5,6], [7,8], [15]

แนวทางการแก้ปัญหา (Two Pointers / Sliding Window)

ใช้ 2 จุด begin และ end ขยาย end สะสมผลรวม เมื่อผลรวม ≥ n ให้เลื่อน begin ลดผลรวม จนกว่าผลรวม < n นับครั้งที่ผลรวม == n

การนำไปใช้ (Implementation)

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

int solve(int n) {
    int begin = 1, end = 1;
    int x = (n + 1) / 2; // end ไม่ต้องเกิน (n+1)/2
    long long sum = 0;
    int count = 0;
    
    while (end <= x) {
        sum += end;
        while (sum >= n) {
            if (sum == n) count++;
            sum -= begin;
            begin++;
        }
        end++;
    }
    return count + 1; // +1 สำหรับ [n] เอง
}

int main() {
    cout << solve(15);
    return 0;
}

อินพุต

15

เอาต์พุต

4

คำอธิบายเพิ่มเติม: สูตรคณิตศาสตร์: จำนวนวิธี = จำนวนตัวหารคี่ของ n (ยกเว้น 1) + 1 หรือเทียบเท่ากับจำนวนวิธีเขียน n = k × m โดย k คี่