# CSES - Collecting Numbers

1st traversal : 1 3
2nd traversal : 2 4

`Your task is to collect the numbers from 1 to n in increasing order`
1st transversal: 1
2nd transversal: 2
3rd transversal: 3 4

what should be the output for:

I/P: 3 2 1 5 4

1st traversal :- 1
2nd traversal :- 2
3rd traversal :- 3 4
4th traversal :- 5

The question statement is kinda confusing it is saying we have to overall pick number in ascending order.

Try to do this way.
suppose you picked
1st traversal :- 1
2nd traversal :- 2 4
3rd travesal :- 3 5
and form and array
1 2 4 3 5 But this is not question wanted us to solve. Basically, question wants us to pick consecutively then only will valid.

1 Like

@cubefreak777 I think what @lriuui0x0 is asking is suppose there are rounds like this:
… x-2
… x-1, x
So till here, I have chosen all numbers in ascending order. Meaning x-2 was put in one round, then pos(x-1) < pos(x-2) so it was put in new round. Then pos(x) > pos(x-1) so it was put in same round as x-1. Now, for x+1, suppose pos(x+1) < pos(x). According to your algo, x+1 would go in a new round. But what if pos(x+1) > pos(x-2) ?? It could have gone in the round that has x-2. But instead, we created a new round.

How can we be sure this doesn’t happen?

Because all we know is pos(x-1) < pos(x-2) and pos(x-1) < pos(x) but we don’t know the relation between pos(x) and pos(x-2). It could be that pos(x) > pos(x-2) and now when we choose x+1, it may be that pos(x+1) < pos(x) but it could be pos(x+1) > pos(x-2)