Grade 10 · Divide and conquerCitește în română

Sum of the elements with divide and conquer

Original: Suma elementelor prin divide et impera

O(n)C++1747 lines2 examples

The idea

The sum of the portion [st, dr] is the sum of the left half [st, m] plus the sum of the right half [m + 1, dr]. A portion with a single element has a sum equal to that element. We also print the number of calls: for n elements there are always 2n - 1 calls (n leaves and n - 1 splitting nodes).

Original description (Romanian)

Suma porțiunii [st, dr] este suma jumătății stângi [st, m] plus suma jumătății drepte [m + 1, dr]. O porțiune cu un singur element are suma egală cu acel element. Afișăm și numărul de apeluri: pentru n elemente se fac mereu 2n - 1 apeluri (n frunze și n - 1 noduri care împart).

Complexity
O(n)
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

5
1 2 3 4 5

Expected output

15 9
Example 2

Input

4
10 -20 30 -40

Expected output

-20 7

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

suma-elementelor.cpp
/*
 * Titlu: Suma elementelor prin divide et impera
 * Clasa: 10
 * Capitol: Divide et impera
 * Descriere: Suma porțiunii [st, dr] este suma jumătății stângi [st, m] plus suma
 *            jumătății drepte [m + 1, dr]. O porțiune cu un singur element are suma
 *            egală cu acel element. Afișăm și numărul de apeluri: pentru n elemente
 *            se fac mereu 2n - 1 apeluri (n frunze și n - 1 noduri care împart).
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 5
 * 1 2 3 4 5
 * Ieșire: 15 9
 *
 * Exemplu
 * Intrare:
 * 4
 * 10 -20 30 -40
 * Ieșire: -20 7
 */
#include <iostream>
using namespace std;

int v[1000], apeluri;

long long suma(int st, int dr)
{
    apeluri++;
    if (st == dr)
        return v[st];
    int m = (st + dr) / 2;
    return suma(st, m) + suma(m + 1, dr);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    long long s = suma(0, n - 1);
    cout << s << ' ' << apeluri << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.