Carvans Solution

Problem

You’re given the maximum speed of N cars in the order they entered the long straight segment of the circuit. Each car prefers to move at its maximum speed. If that’s not possible because of the front car being slow, it might have to lower its speed. It still moves at the fastest possible speed while avoiding any collisions. For the purpose of this problem, you can assume that the straight segment is infinitely long.

Count the number of cars which were moving at their maximum speed on the straight segment.

CodeChef Problem Link

Input

The first line of the input contains a single integer T denoting the number of test cases to follow. Description of each test case contains 2 lines. The first of these lines contain a single integer N, the number of cars. The second line contains N space separated integers, denoting the maximum speed of the cars in the order they entered the long straight segment.

Output

For each test case, output a single line containing the number of cars which were moving at their maximum speed on the segment.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 10,000

Sample Input

1
5
4 5 1 2 3

Sample Output

2

Solution

Code Implementation

//
//  main.cpp
//  Carvans
//
//  Created by Himanshu on 15/02/22.
//

#include <iostream>
using namespace std;

int main() {
    int T,  n,  ans, a[10000];
    cin>>T;

    while(T>0) {
        ans=1;
        cin>>n;

        for(int i=0; i<n; i++) {
            cin>>a[i];
        }

        for(int i=0; i<n-1; i++) {
            //adding ith car to the solution(ans) if car ahead of
            //it has slower speed
            if(a[i]>a[i+1]) {
                ans++;
            } else {
                
                //copying slower speed car for the next iteration,
                //since that is the maximum speed of i+1th car now
                a[i+1]=a[i];
            }
        }

        cout<<ans<<endl;

        T--;
    }

    return 0;
}

Time Complexity: O(n) (n is the number of array elements)