9,093 views
9 votes
9 votes

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$

3 Answers

Best answer
14 votes
14 votes

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.

selected by
3 votes
3 votes
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.
0 votes
0 votes

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



Additional information:

  • 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.
Answer:

Related questions

11 votes
11 votes
2 answers
1
makhdoom ghaya asked Apr 25, 2016
7,821 views
Let $A(1:8, -5:5, -10:5)$ be a three dimensional array. How many elements are there in the array $A$?$1200$$1408$$33$$1050$
3 votes
3 votes
2 answers
2
makhdoom ghaya asked Apr 27, 2016
6,155 views
Which of the following number of nodes can form a full binary tree?8151413
5 votes
5 votes
2 answers
3
makhdoom ghaya asked Apr 25, 2016
6,591 views
The following steps in a linked listp = getnode() info(p) = 10 next (p) = list list = presult in which type of operation?Pop operation in stackRemoval of a nodeInserting ...
10 votes
10 votes
2 answers
4
makhdoom ghaya asked Apr 25, 2016
8,376 views
The number of rotations required to insert a sequence of elements $9, 6, 5, 8, 7, 10$ into an empty $AVL$ tree is?$0$$1$$2$$3$