Grade 9 · Number sequences read one at a timeCitește în română

Number of sign changes

Original: Numărul de schimbări de semn

O(n)C++1737 lines1 example

The idea

n non-zero numbers are read. A sign change happens between two consecutive terms with opposite signs, i.e. when their product is negative. We compare the signs (ant < 0) != (x < 0) instead of multiplying, so the product cannot overflow the data type.

Original description (Romanian)

Se citesc n numere nenule. O schimbare de semn are loc între doi termeni consecutivi de semne opuse, adică atunci când produsul lor este negativ. Comparăm semnele (ant < 0) != (x < 0) în loc să înmulțim, ca produsul să nu depășească tipul de date.

Complexity: O(n)
Grade: Grade 9 (Clasa a IX-a)
Chapter: Number sequences read one at a time

Examples

Example 1

Input

7
3 -1 -4 2 5 -6 8

Expected output

The code

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

numarul-de-schimbari-de-semn.cpp

/*
 * Titlu: Numărul de schimbări de semn
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: Se citesc n numere nenule. O schimbare de semn are loc între doi
 *            termeni consecutivi de semne opuse, adică atunci când produsul lor
 *            este negativ. Comparăm semnele (ant < 0) != (x < 0) în loc să
 *            înmulțim, ca produsul să nu depășească tipul de date.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 7
 * 3 -1 -4 2 5 -6 8
 * Ieșire: 4
 */
#include <iostream>
using namespace std;

int main()
{
    int n, schimbari = 0;
    long long ant, x;
    cin >> n >> ant;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        if ((ant < 0) != (x < 0))
        {
            schimbari++;
        }
        ant = x;
    }
    cout << schimbari << '\n';
    return 0;
}

Input (stdin)

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