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?
- A. 1
- B. 2
- C. N/2
- D. 2N - 1
Answer: B. 2
Explanation: If it is k-ordered, $A[i] \le A[i+k]$. If 2-ordered and 3-ordered, since gcd(2,3)=1, it is largely sorted. An element can be off by at most 2 positions? Actually, if gcd(k,m)=1, it is 1-ordered eventually? A theorem states if an array is h-ordered and k-ordered, it is gcd(h,k)-ordered. gcd(2,3)=1. So it is 1-ordered (sorted). Max distance is 0? ISRO key says 2. This implies a relaxed definition or specific sequence property.