Last Updated: 22 Apr, 2021
Collect The Numbers
Moderate
Asked in company
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.
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
Approaches
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.
- We will check if ARR[index] is equal to currentNumber,
- Increment totalRounds by 1.
- Iterate index till 0 to N-1,
- Return the variable totalRounds.
The idea is to observe the fact that whenever the number val occurs before val+1, we can always take both of them in a single round, but if val comes after val+1, we cannot take them in the single round, and we will need to make an extra round to collect val+1. We will use this idea to find the total number of rounds to collect all numbers.
Our approach will be to construct array positions, which will store the index of all elements in the array ARR and maintain a variable numberIndex, which stores the value of the index at which we are currently present in the ARR. We will initialize numberIndex as 0. We will iterate currentNumber from 1 to N. We will find the index of currentNumber with the help of the array positions. Now, there will be two cases,
- If the index of currentNumber is greater than numberIndex, then we can collect both numbers in a single round. So, we will update numberIndex with the index of currentNumber.
- If the index of currentNumber is smaller than numberIndex, then we cannot collect both numbers in a single round. We need to make an extra round to collect currentNumber. So, we will increment the total number of rounds by 1 and update numberIndex with the index of currentNumber.
In the end, we will return the total number of rounds that we required to collect all numbers.
Algorithm:
- We will set totalRounds as 1 and numberIndex as 0. The variable totalRounds stores the total number of rounds required to collect all numbers from 1 to N. The variable numberIndex stores the value of the index at which we are currently present in the ARR.
- Create array positions of size N+1, which will store the index of all elements present in the array ARR.
- Iterate index from 0 to N-1,
- Assign the ARR[index] into the array positions with index as its value.
- Iterate currentNumber from 1 to N,
- Find the index of currentNumber in the array ARR with the help of the array positions, which is equal to positions[currentNumber].
- Check if the index of currentNumber is less than numberIndex,
- Increment totalRounds by 1.
- Update the value of numberIndex with the index of currentNumber.
- Return the variable totalRounds.