Collect The Numbers

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in company
OYO

Problem statement

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 to N exactly once. Your task is to find the minimum total number of rounds required to collect all the numbers from 1 to N in increasing order present in the array ‘ARR’. On each round, you can traverse through the array ‘ARR’ from left to right and collect as many numbers as possible in increasing order.

For example :

Consider the array ARR = [4, 5, 1, 2, 3], we will collect 1,2 and 3 in the first round, and the array ARR after the first round will be [4, 5]. Finally, we will collect 4 and 5 in the second round. The minimum total number of rounds required is 2. Hence, the answer is 2 in this case.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains a single integer, 'N', denoting the number of elements in the array.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format :

For each test case, print a single integer - the minimum total number of rounds required to collect the numbers from 1 to ‘N’  in increasing order.

Print the output of each test case in a separate line.

Constraints :

1 <=  T  <= 10
1 <=  N <= 10^5
1 <=  ARR[i]  <= N

All elements present in the array ARR are unique.

Time limit: 1 sec

Sample Input 1 :

2
3 
2 1 3
3
3 2 1

Sample Output 1 :

2
3
Explanation of sample input 1 :
For the first test case, 
We will collect 1 in the first round, and the array ARR after the first round will be [2,3]. Finally, we will collect 2 and 3 in the second round. The minimum total number of rounds required is 2. Hence, the answer is 2 in this case.

For the second test case,
We will collect 1 in the first round, and the array ARR after the first round will be [3, 2]. Similarly, we will collect 2 in the second round, and the ARR will be [3]. Finally, we will collect 3 in the third round. The minimum total number of rounds required is 3. Hence, the answer is 3 in this case.

Sample Input 2 :

2
5
4 2 1 5 3
5
1 2 3 4 5

Sample Output 2 :

3
1
Hint

Traverse through the array in the described manner and collect as many numbers as possible in each round.

Approaches (2)
Brute Force Approach

A simple method is to traverse through the array ARR on each round until we have collected all numbers from 1 to N in increasing order. 

Therefore, we will maintain a variable currentNumber, which stores the element’s value, which we are trying to collect from the ARR. On each round, we will iterate index from 0 to N-1, and we will check if the ARR[index] is equal to currentNumber, then we will increment currentNumber by 1. After each round, we will check if all numbers are collected. If all numbers are not collected from the ARR, then we will perform another round. In the end, we will return the total number of rounds that we required to collect all numbers. 

 

Algorithm:

  • We will set totalRounds as 0. The variable totalRounds stores the total number of rounds required to collect all numbers from 1 to N.
  • We will set the variable currentNumber as 1. The variable currentNumber stores the value of the number, which we are trying to collect from the ARR.
  • Iterate till currentNumber is less than or equal to N,
    • Iterate index till 0 to N-1,
      • We will check if ARR[index] is equal to currentNumber,
        • We will Increment currentNumber by 1.
    • Increment totalRounds by 1.
  • Return the variable totalRounds.
Time Complexity

O(N^2), where N denotes the number of elements in the array.

 

In the worst case, when all numbers are present in the array in decreasing order, we are doing N iterations, and in each iteration, it takes O(N) time to traverse through the array ARR to collect numbers. Hence, the overall Time Complexity is O(N^2).

Space Complexity

O(1). 

 

Constant space is being used. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Collect The Numbers
Full screen
Console