The Gateway to Computer Science Excellence
0 votes

in Programming by Boss (11.1k points) | 659 views

1 Answer

+4 votes
Best answer

If the array is 1-ordered, it means that It is an array of ascending order. This is the only chance that it can be of 1-ordered.

It means that if array has 2N element and 1-ordered then its element can be of [1,2,3,4,5,...........,2N-1,2N].

Now an array can be 2-ordered only when its odd position is 1-ordered with odd position and even position is 1-ordered with even position element. So it can be arranged like this. [N+1,1,N+2,2,N+3,3,N+4,4,N+5,5,..........,N-2,2N-2,N-1,2N-1,N,2N].

So the maximum number of position difference can be N. ( See the First Element of both the array).

So, Option (e) is correct.


The first element has to be <= the 3rd, 5th, ... elements by the 2-orderedness and <= the 4th,6th,... elements by the 3-orderedness and the 2-orderedness combined. So it has to be in either the 1st or 2nd position.
Suppose that the first element (if any) not in its usual position is the kth element. Then it has to be in position k+1 by a similar argument.
Now consider what must be in position k - it has to be k+1. If not it is bigger than k+1 and comes at least 2 before k+1 in the list, acontradiction.
So at worst k,k+1 have swapped places. Then the first k+1 places can not effect the remainder of the list (as
they must all be less than any element in the remainder of the list) so we can repeat the same argument further on. Thus the answer must be (d) i.e.1.
So the answer is (d).
by Boss (35.7k points)
selected by
Please explain in detail with example what is k-ordered array

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,375 answers
105,289 users