Arithmetic triangle - solution


Before you look at the solution

First try to solve the task on your own. Even if you do not reach a complete solution, trying to develop an idea is very important for developing algorithmic thinking.

Introduction

This example shows the difference between an educational (simulation) approach and an efficient mathematical formula. The goal is to understand how the rows of the triangle are built, how the first and the last number of a row follow from that and, finally, the sum of a row. First we show Solution 1, which "builds" the triangle row by row, and then Solution 2, which reaches the result directly, with a formula.


Task text

What is the sum of the numbers in a given row of the following triangle?

         1
      2  3  4
   5  6  7  8  9
10 11 12 13 14 15 16
        ...

Input

The number n of rows for which the sum should be computed is read from standard input (1 ≤ n ≤ 50 000). After that, n row numbers k (1 ≤ k ≤ 5·104) whose sums should be computed are read. Row numbering starts from 1.

Output

For every query, in a separate line, print the sum of the numbers in the given row of the triangle.

Example

Input:
3
1
2
3

Output:
1
9
35

The first row contains only the number 1, the second row 2 + 3 + 4 = 9, and the third row 5 + 6 + 7 + 8 + 9 = 35.


Solution 1 — simulation (educational) approach

This solution simulates building the triangle row by row. For the required row k, the number of elements per row (1, 3, 5, ...) is increased iteratively until we reach the required row.

The advantage of this approach is its simplicity and clarity, but the time complexity is O(k) per query.

Show / hide solution 1
#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    // Reading the number of queries
    if (!(cin >> n))
        return 0;

    vector<int> rows(n);

    // Reading the required rows
    for (int i = 0; i < n; ++i)
        cin >> rows[i];

    // Processing every query separately
    for (int idx = 0; idx < n; ++idx) {

        // The row whose sum we are looking for
        int k = rows[idx];

        // Number of elements in the current row
        long long number_of_elements = 0;

        // First number in the row
        long long a_first = 0;

        // Last number in the row
        long long a_last = 0;

        // Sum of the required row
        long long row_sum = 0;

        // We build the triangle iteratively up to the k-th row
        for (int j = 1; j <= k; ++j) {

            // Every row has 2 elements more than the previous one
            if (j == 1)
                number_of_elements = 1;
            else
                number_of_elements += 2;

            // The first element of the row is 1 greater
            // than the last element of the previous row
            a_first = a_last + 1;

            // The last element of the row
            a_last = a_first + (number_of_elements - 1);

            // When we reach the required row
            if (j == k) {

                // Formula for the sum of an arithmetic progression
                row_sum = (a_first + a_last) * number_of_elements / 2;

                cout << row_sum << '\n';
            }
        }
    }

    return 0;
}

Weaknesses of solution 1 and what should be fixed


Solution 2 — efficient mathematical solution

Unlike the simulation, here we look for a mathematical pattern so that we can directly compute the number of elements in a row, the first number, the last number and the sum of the row, without building the triangle. This gives a solution with time complexity O(1) per query.

Let r be the row whose sum we want (in the code it is nr[i]).

1. The number of elements in the r-th row

The rows contain an odd number of elements, so:

k = 2r − 1

For example, for r = 3 we get k = 5.

2. The total number of elements in the previous r − 1 rows

This is the sum of the first r − 1 odd numbers:

T = 1 + 3 + 5 + ... + (2(r − 1) − 1)

The numbers 1, 3, 5, ... form an arithmetic progression with first term a1 = 1, difference d = 2 and r − 1 terms. The last term is 1 + (r − 2)·2 = 2r − 3, so the sum is:

T = (1 + (2r − 3)) · (r − 1) / 2 = (2r − 2) · (r − 1) / 2 = (r − 1)²

For r = 3 we get T = 4: there are four numbers before the third row (1, 2, 3, 4).

3. The first number in the r-th row

a1 = T + 1 = (r − 1)² + 1

For r = 3 we get a1 = 5.

4. The last number in the r-th row

The numbers in a row grow by 1, so an = a1 + (k − 1). More simply, the last number of the r-th row is equal to the total number of elements in the first r rows:

an = r²

For r = 3 we get an = 9.

5. The sum of the r-th row

S = (a1 + an) · k / 2 = ((r − 1)² + 1 + r²) · (2r − 1) / 2

Since (r − 1)² + 1 + r² = 2r² − 2r + 2, the expression simplifies to:

S = (r² − r + 1) · (2r − 1)

Checking the example (r = 3)

a1 = 5, an = 9, k = 5, so S = (5 + 9) · 5 / 2 = 35. From the simplified formula: (9 − 3 + 1) · 5 = 7 · 5 = 35.

Show / hide solution 2
#include <iostream>
#include <vector>

using namespace std;

/*
Efficient mathematical solution

Variables:
- r   -> the required row
- k   -> number of elements in the row
- T   -> number of elements in the previous rows
- a1  -> first number of the row
- an  -> last number of the row
- S   -> sum of the row
*/

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    // Number of queries
    if (!(cin >> n))
        return 0;

    vector<int> nr(n);

    // Reading the rows
    for (int i = 0; i < n; ++i) {
        cin >> nr[i];
    }

    long long a1 = 0;
    long long an = 0;
    long long S = 0;

    long long d = 1;  // difference between neighbouring numbers in a row

    for (int i = 0; i < n; ++i) {

        long long r = nr[i];

        // Number of elements in the row
        long long k = 2 * r - 1;

        // Number of elements up to the previous row
        long long T = (r - 1) * (r - 1);

        // First number of the row
        a1 = T + 1;

        // Last number of the row
        an = a1 + (k - 1) * d;

        // Sum of the row
        S = (a1 + an) * k / 2;

        cout << S << '\n';
    }

    return 0;
}

Explanation of the important parts of the program


Complexity of the solutions

Conclusion

The task shows how observing the first few rows leads to a general formula. The key steps are the sum of the first odd numbers, (r − 1)², and the formula for the sum of an arithmetic progression. When the problem is solved for a large number of queries, the mathematical O(1) solution is the one that passes all tests.