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

Checking a non-decreasing sequence

Original: Verificarea unui șir crescător

O(n)C++1752 lines2 examples

The idea

The sequence is non-decreasing if every number is at least equal to the one before it. We keep the previous number in the variable ant and compare every new number with it. We still read the whole sequence, even if we have already found a bad pair. For 'strictly increasing' the condition becomes x <= ant.

Original description (Romanian)

Șirul este crescător dacă fiecare număr este cel puțin egal cu cel dinaintea lui. Păstrăm numărul anterior în variabila ant și comparăm fiecare număr nou cu el. Citim totuși tot șirul, chiar dacă am găsit deja o pereche greșită. Pentru „strict crescător” condiția devine x <= ant.

Complexity
O(n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

5
1 3 3 7 9

Expected output

DA
Example 2

Input

4
2 5 4 8

Expected output

NU

The code

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

sir-crescator.cpp
/*
 * Titlu: Verificarea unui șir crescător
 * Clasa: 9
 * Capitol: Șiruri de numere citite pe rând
 * Descriere: Șirul este crescător dacă fiecare număr este cel puțin egal cu
 *            cel dinaintea lui. Păstrăm numărul anterior în variabila ant și
 *            comparăm fiecare număr nou cu el. Citim totuși tot șirul, chiar
 *            dacă am găsit deja o pereche greșită. Pentru „strict crescător”
 *            condiția devine x <= ant.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 5
 * 1 3 3 7 9
 * Ieșire: DA
 *
 * Exemplu
 * Intrare:
 * 4
 * 2 5 4 8
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long ant, x;
    bool crescator = true;
    cin >> n >> ant;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        if (x < ant)
        {
            crescator = false;
        }
        ant = x;
    }
    if (crescator)
    {
        cout << "DA" << '\n';
    }
    else
    {
        cout << "NU" << '\n';
    }
    return 0;
}

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