4.7k views

In an array of $2N$ elements that is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from its position if the array were 1-ordered?

1. $1$
2. $2$
3. $N/2$
4. $2N - 1$
in DS | 4.7k views
+8

A=[1,4,2,6,3,7,5,8] is a 2 ordered array while A=[1,4,2,5,3,6,8,7,9,10] is also a 2 ordered array… An array is called k-ordered if any one of it’s element is at most k places away from its position in the sorted array…

eg. A=[1 4 2 6 3 7 5 8]

…A=[1 2 3 4 5 6 7 8]

………[0 1 2 2 2 2 1 0] is the difference in the positions of respective elements… So it is a 2 ordered array as the max difference is 2….

A=[1 4 2 5 3 6 8 7 9 10]

A=[1 2 3 4 5 6 7 8 9 10]

…..[0 1 2 2 1 0 1 1 0 0]…. Here also the max difference is 2.. So it is also a 2 ordered array….

While [1 3 2 5 4 7 6 8] is a 1 ordered array…

ans is A) 1

0

An array A [ 1 … n] is said to be k-ordered if
A [i - k] < A [ i ] < A [i + k] for each i such that k < i < n – k.

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, a
contradiction. 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.

For example, the array 1 4 2 6 3 7 5 8 is 2- ordered.

Now come to question

Array is both 2 ordered and 3 ordered.i.e.

1 2 3 5 4 6 7 8

Now  if the array were 1-ordered then  array will be 1 2 3 4 5 6 7 8

maximum number of positions that an element can be from its position=1

So  i think option A is correct.

by Boss (38.7k points)
selected
0

Yes you are correct answer is A,

But could you please explain how the 2 , 3 ordered array and 1 ordered array is same in your explanation.

0
@manojK i did get ur explanation

0
wrong [email protected] correct it..or i shud tell u
0
0
0
i will post the verification in comment...and after wards ....let manoj...update his answer wait 4 a min..m posting it..
0

@shivani if take we array the 1 2 3 4 5 6 7 8 which 2 & 3 sorted then we won't get the distance one..lets take manoj's way

2&3 sorted              1 2 3 4 5 6 7 8

1 sorted                  1 2 3 4 5 6 7 8

distance                    0 0 0 0 0 0 0 0   all are at same position

now if we take the array 2& 3   1 2 3 4 6 7 8

2&3 sorted              1 2 3 4 6 7 8

1 sorted                  1 2 3 4 5 6 7 8      4  & 5 are at 1-distance..away..from there

distance                  0 0 0 1 1 0 0 0           location

now shivani u can see..both 4 & 5 are at 1- distance

0
how to get 2 and 3 ordered array can anyone tell me?
0

@manoj, If I refer expression given by you.

An array A [ 1 … n] is said to be k-ordered if
A [i - k] < A [ i ] < A [i + k] for each i such that k < i < n – k.

1st thing :  What is 'i' here??

2nd thing: how to get 2 order and 3 order array...????

no no...my corrected question is "How to get k ordered ARRAY" ?????

0

$4,2,8,6,21,22,28,26$

whose $1$ order is ---> $2,4,6,8,21,22,26,28$
0
it is right
+1 vote
This is very easy question. no any confusion should be there. Earlier, I also thought that answer might be 2 as I was reasoning that if array were 1 sorted, then suppose element value 3 could be at positions 2nd or 4th. but, the question is asking something else.

correct procedure to solve this question is:

question is saying that array is 2 sorted as well as 3 sorted means the array is 2 sorted.

let us consider array with N = 3.

2  1  4  3  6  5     the array is 1 sorted.

now, pick any element from above array let us say we are picking element 3, it might at position 3rd not at 5th position starting from beginning because if element 3 if it would be at position 5th , then the resulting array would not be 1 sorted. that's why it might be at position 3rd.Therefore, maximum positions element can be, is one.

See, easy question, na. very easy question. nothing to panic. read question patiently. You'll definitely solve the answer.
by (345 points)

This question literally asks the definition of 1-ordered array. In a k-ordered (also called k-sorted) array each element is at most k positions away from it's sorted position.

So, a 1-ordered array is 1 position away from it's sorted position. Option A

• To sort an unsorted array, a good sorting algorithm usually takes O(nlogn) time; but to sort a k-sorted array, the same will take O(nlogk) time.
by Loyal (6.4k points)