CSES Solutions – Collecting Numbers
You are given an array arr[] 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?
Examples:
Input: N = 5, arr[] = {4, 2, 1, 5, 3}
Output: 3
Explanation:
- In the first round, we collect {1}.
- In the second round, we collect {2, 3}.
- In the third round, we collect {4, 5}.
Input: N = 4, arr[] = {2, 1, 4, 3}
Output: 3
Explanation:
- In the first round, we collect {1}.
- In the second round, we collect {2, 3}.
- In the third round, we collect {4}.
Approach: To solve the problem, follow the below idea:
The problem states that we have to collect numbers from 1 to N in increasing order. So, it means that we have to collect numbers strictly in the order: 1, 2, 3, 4 …. N. We cannot collect 1 and 3 in one round and then 2 in the next round. In other words, for every number X > 1, we cannot collect X if (X – 1) hasn’t been collected yet.
The idea to solve the problem is: If the number X occurs before X + 1 then we can collect both X and X + 1 in a single round. Otherwise, if X comes after X + 1 then we cannot take them in the single round hence we add 1 to the final answer. Initially, we store the indices of all the elements. Now, for every number X from 1 to N – 1, check if X + 1 occurs before or after X in the array arr[]. If X + 1 occurs before X, we can increment the answer by 1.
Step-by-step algorithm:
- Maintain an array indices[] of size N + 1 to store the index of all the elements.
- Declare a variable ans to store the total number of rounds.
- For every number num from 1 to N – 1, check if (num + 1) has index lesser or greater.
- If the index of (num + 1) is less than index of num, this means that they both will be collected in different rounds, so we increment ans by 1.
- After comparing all the numbers, return the final answer as ans.
Below is the implementation of the algorithm:
#include <iostream>
#include <vector>
using namespace std;
// Function to find the number of rounds
long solve(long arr[], int N) {
// Variable to store the final answer
long ans = 1;
// Array to store the index of numbers from 1 to N
vector<long> indices(N + 1);
// Store the index of all elements of arr[]
for (int i = 0; i < N; i++) {
indices[arr[i]] = i;
}
// If num occurs after (num + 1), increment ans by 1
for (int num = 1; num < N; num++) {
if (indices[num + 1] < indices[num])
ans++;
}
return ans;
}
int main() {
// Sample Input
int N = 4;
long arr[] = { 2, 1, 4, 3 };
cout << solve(arr, N) << endl;
return 0;
}
import java.util.Arrays;
public class NumberOfRounds {
// Function to find the number of rounds
static long solve(long[] arr, int N)
{
// Variable to store the final answer
long ans = 1;
// Array to store the index of numbers from 1 to N
long[] indices = new long[N + 1];
// Store the index of all elements of arr[]
for (int i = 0; i < N; i++) {
indices[(int)arr[i]] = i;
}
// If num occurs after (num + 1), increment ans by 1
for (int num = 1; num < N; num++) {
if (indices[num + 1] < indices[num])
ans++;
}
return ans;
}
public static void main(String[] args)
{
// Sample Input
int N = 4;
long[] arr = { 2, 1, 4, 3 };
System.out.println(solve(arr, N));
}
}
// This code is contributed by rambabuguphka
using System;
public class Program
{
// Function to find the number of rounds
static long Solve(long[] arr, int N)
{
// Variable to store the final answer
long ans = 1;
// Array to store the index of numbers from 1 to N
long[] indices = new long[N + 1];
// Store the index of all elements of arr[]
for (int i = 0; i < N; i++)
{
indices[arr[i]] = i;
}
// If num occurs after (num + 1), increment ans by 1
for (int num = 1; num < N; num++)
{
if (indices[num + 1] < indices[num])
ans++;
}
return ans;
}
public static void Main()
{
// Sample Input
int N = 4;
long[] arr = { 2, 1, 4, 3 };
Console.WriteLine(Solve(arr, N));
}
}
// This code is contributed by shivamgupta0987654321
// function to find the number of rounds
function solve(arr) {
// Variable to store the final answer
let ans = 1;
// Array to store the index of numbers from 1 to N
const indices = new Array(arr.length + 1);
// Store the index of all elements of arr[]
for (let i = 0; i < arr.length; i++) {
indices[arr[i]] = i;
}
// If num occurs after (num + 1), increment ans by 1
for (let num = 1; num < arr.length; num++) {
if (indices[num + 1] < indices[num]) {
ans++;
}
}
return ans;
}
// Sample Input
const arr = [2, 1, 4, 3];
console.log(solve(arr));
// This code is contributed by Ayush Mishra
# function to find the number of rounds
def solve(arr, N):
# Variable to store the final answer
ans = 1
# Array to store the index of numbers from 1 to N
indices = [0] * (N + 1)
# Store the index of all elements of arr[]
for i in range(N):
indices[arr[i]] = i
# If num occurs after (num + 1), increment ans by 1
for num in range(1, N):
if indices[num + 1] < indices[num]:
ans += 1
return ans
# Sample Input
N = 4
arr = [2, 1, 4, 3]
print(solve(arr, N))
Output
3
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(N)