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

Counting the even elements with divide and conquer

Original: Numărul elementelor pare prin divide et impera

O(n)C++1746 lines2 examples

The idea

The same pattern as for the sum: the result for the portion [st, dr] is the sum of the results of the two halves. Only the base case differs: a portion with a single element contributes 1 if the element is even and 0 otherwise. The pattern adapts to any counting (prime elements, negative ones, ones divisible by k, etc.).

Original description (Romanian)

Același tipar ca la sumă: rezultatul pentru porțiunea [st, dr] este suma rezultatelor celor două jumătăți. Diferă doar cazul elementar: o porțiune cu un singur element contribuie cu 1 dacă elementul este par și cu 0 altfel. Tiparul se poate adapta la orice numărare (elemente prime, negative, divizibile cu k etc.).

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

Examples

Example 1

Input

6
1 2 3 4 6 7

Expected output

3
Example 2

Input

3
1 3 5

Expected output

0

The code

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

numarul-elementelor-pare.cpp
/*
 * Titlu: Numărul elementelor pare prin divide et impera
 * Clasa: 10
 * Capitol: Divide et impera
 * Descriere: Același tipar ca la sumă: rezultatul pentru porțiunea [st, dr] este
 *            suma rezultatelor celor două jumătăți. Diferă doar cazul elementar:
 *            o porțiune cu un singur element contribuie cu 1 dacă elementul este
 *            par și cu 0 altfel. Tiparul se poate adapta la orice numărare (elemente
 *            prime, negative, divizibile cu k etc.).
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 6
 * 1 2 3 4 6 7
 * Ieșire: 3
 *
 * Exemplu
 * Intrare:
 * 3
 * 1 3 5
 * Ieșire: 0
 */
#include <iostream>
using namespace std;

int v[1000];

int numarPare(int st, int dr)
{
    if (st == dr)
        return v[st] % 2 == 0 ? 1 : 0;
    int m = (st + dr) / 2;
    return numarPare(st, m) + numarPare(m + 1, dr);
}

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

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