[C/C++] BOJ #1024 - Sum of Number Sequences.

The problem “Sum of Number Sequences” (Baekjoon #1024) requires finding a sequence of consecutive integers whose sum equals a given number N, while ensuring that the length of the sequence is at least L. If multiple valid sequences exist, the shortest one should be chosen. If no such sequence can be found, the program should return -1.

 

---

 

The sum of a sequence depends on how the sequence is structured. Common types of sequences, such as arithmetic and geometric sequences, have formulas to calculate their sums. Since this problem requires finding the sum of a sequence of consecutive numbers, we can use the formula for the sum of an arithmetic sequence.

The sum of the sequence differs depending on whether its length is even or odd. If the initial term is s and the length of the sequence is n, the sum can be expressed as follows:

 

\[s + (s+1) + … + (s+(n-1)) = \frac{n(2s+n-1)}{2}\]

 

If n is odd, the value of \(2s + n - 1\) is even. The expression \(\frac{2s + n - 1}{2}\) represents the average of this sequence, which must be a natural number. If the average is not a natural number, then a sequence of length n cannot exist.

 

Similarly, if n is even, the value of \(2s + n - 1\) is odd, meaning that the average is not a natural number, but the remainder when divided by n is n/2. If the remainder is not n/2, then a sequence of length n cannot exist.

 

Using this approach, I was able to solve the problem. It might be possible to design a more optimized algorithm, but that would require factorizing n, which does not seem like an efficient approach. Factorizing and matching values would be tedious as well. Therefore, within this kind of algorithm, I implemented a relatively brute-force method.

 

---

a sequence of consecutive numbers

---

 

Below is the code I wrote. Please use it for reference only.

//----------------------------------------------------------
//    baekjoon #1024 - Sum of Number Sequences.
//        - by Aubrey Choi
//        - created at 2019-07-03
//----------------------------------------------------------
#include <stdio.h>

int main()
{
    int n, s;
    scanf("%d%d", &n, &s);
    for(; s*(s-1) <= 2*n && s <= 100; s++)
    {
        if((s & 1) && (n%s == 0))
        {
            for(int i = n/s-s / 2; i <= n/s+s / 2; i++)
                printf("%d ", i);
            putchar('\n');
            break;
        }
        if(!(s & 1) && (n % s == s/2))
        {
            for(int i = n/s - s/2 + 1; i <= n/s + s/2; i++)
                printf("%d ", i);
            putchar('\n');
            break;
        }
    }
    if(s*(s - 1) > 2 * n || s > 100) puts("-1");
    return 0;
}