# k-ordered array problem

An array $$A[1...n]$$ is said to be k-ordered if

$$A[i - k] \leq A[i] \leq A[i + k]$$

for all $$i$$ such that $$k < i \leq n - k$$.

For example, the array $$A = [1, 4, 2, 6, 3, 7, 5, 8]$$ is 2 ordered.

Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n


Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n


I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.

Can someone please explain to me the meaning of the questions in simple terms?

Thanks!

P.S. First time questioner here. Sorry if I missed anything.

Take your example $$A = [1,4,2,6,3,7,5,8].$$ An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together: $$1,4,2,6,3,7,5,8 \\ 1,2,3,4,5,6,7,8$$ You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.

• Thanks for the answer! So, if I am correct, the Q1's answer is n/2 ?? May 18, 2014 at 18:05
• @GaurangTandon I don't know. Not that you understand the question, you should be more confident in the answer. Try to convince yourself that your answer is correct. May 19, 2014 at 0:43
• I think I got it: Q1 = 2, and Q2 = 1, and the array both 3-ordered and 2-ordered is [1, 2, 3, 5, 4, 6, 7, 8]. I think now that this is indeed the correct answer. May 19, 2014 at 12:41

2.) Suppose A=[1,2,3,4,5,6,7,8,9,10] index from 1-10. k=3 from condition 3 < i <=10-3 for i=4,5,6,7

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 4 A[1]<=A[4]<=A[7], i=5 A[2]<=A[5]<=A[8], i= 6 A[3]<=A[6]<=A[9], i=7 A[4]<=A[7]<=A[10]

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

k=2 from condition 2 < i <=10-2 for i=3,4,5,6,7,8

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 3 A[1]<=A[3]<=A[5], i=4 A[2]<=A[4]<=A[6], i= 5 A[3]<=A[5]<=A[7], i=6 A[4]<=A[6]<=A[8], i= 7 A[5]<=A[7]<=A[9], i=8 A[6]<=A[8]<=A[10]

2-ordered A=[1,4,2,5,3,6,8,7,9,10] similarly 1-ordered A=[1,2,3,4,5,6,7,8,9,10]

so maximum position of the element is N/2 (see from 2-ordered A[8]=7 and from 3-ordered A[3]=7 so position = 8-3=5 but total number of element N=10 hence 10/2=5)

Now lets A=[1,2,3,4,5,6,7,8] index from 1-8. k=3 from condition 3 < i <=8-3 for i=4,5

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 4 A[1]<=A[4]<=A[7], i=5 A[2]<=A[5]<=A[8],

3-ordered A=[1,4,7,2,5,8,3,6]

k=2 from condition 2

Applying condition: A[i-k]<=A[i]<=A[i+k] i= 3 A[1]<=A[3]<=A[5], i=4 A[2]<=A[4]<=A[6], i= 5 A[3]<=A[5]<=A[7], i=6 A[4]<=A[6]<=A[8]

2-ordered A=[1,4,2,5,3,6,7,8] similarly 1-ordered A=[1,2,3,4,5,6,7,8]

so maximum position of the element is N/2 (see from 2-ordered A[7]=7 and from 3-ordered A[3]=7 so position = 7-3=4 but total number of element N=8 hence 8/2=4)

Hence (C) N/2

1.) similarly , A=[1,2,3,4,5,6,7,8,9,10] index 1-10 2-ordered A=[1,4,2,5,3,6,8,7,9,10] 1-ordered A=[1,2,3,4,5,6,7,8,9,10]

so maximum position of the element is 2 (2-ordered A[2]=4, 1-ordered A[4]=4 hence position = 4-2=2 or 2-ordered A[5]=3, 1-ordered A[3]=3 hence position = 5-3=2)

Lets A= [1,2,3,4,5,6,7,8] 2-ordered A=[1,4,2,5,3,6,7,8] 1-ordered A=[1,2,3,4,5,6,7,8]

so maximum position of the element is 2 (2-ordered A[2]=4, 1-ordered A[4]=4 hence position = 4-2=2 or 2-ordered A[5]=3, 1-ordered A[3]=3 hence position = 5-3=2)

Hence (b) 2

• I recommend that you use Latex, and proof-read your answer before writing) - as it stands this is a wall of text that is quite imposing.
– D.W.
May 22, 2014 at 21:06