Collecting Numbers

You are given an array that contains each number between 1…n exactly once. Your task is to collect the numbers from 1 to n in increasing order.

On each round, you go through the array from left to right and collect as many numbers as possible. What will be the total number of rounds?

Example:

Input:  n = 5, arr = {4, 2, 1, 5, 3}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int collectingNumbers(int n, vector<int> &arr)
{

    vector<bool> used(n + 1);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];
        ans += !used[x - 1];
        used[x] = true;
    }
    return ans;
}

int main()
{
    int n = 5;
    vector<int> arr = {4, 2, 1, 5, 3};

    cout << collectingNumbers(n, arr) << "\n";

    return 0;
}