# Maximize X such that Array can be sorted by swapping elements X distance apart

Given an input **arr[]** of length **N**, Which contains integers from **1 to N **in unsorted order**. **You can apply only one type of operation on arr[] elements’:

- Choose an index
**i**and an integer**X**and swap A_{i }with an element that is X distance apart and both the indices are within the boundary of the array.

Then the task is to find the maximumvalue of **X** by which all the elements should be at their respective place of sorted order.

**Examples:**

Input:N = 6, arr[] = {6, 2, 3, 4, 5, 1}Output:5Explanation:arr[] can be sorted by exchanging elements at first (A_{1 }= 6)

and last(A_{6 }= 1) index of arr[]. Here value ofXis5and also follows the rule of given operation.

It can be verified that there isno maxvalue rather that5of by which arr[] can be sorted.

Input:N = 6, arr[] = {3, 2, 1, 6, 5, 4}Output:2Explanation:Element at 1_{st}and 3_{rd }index can be swapped

to form the arr[] as = {1, 2,3, 6, 5, 4} and then 4_{th }and 6_{th }

element can be exchanged with each other to make arr[] sorted: {1, 2, 3,4, 5,6}.

For first operation value of X used : 2

For second operation value of X used : 2

Then, Maximum value of X among all operations by which

we can place all elements to their respective sorted position:2

**Approach:** Implement the below idea to solve the problem

Calculate the absolute difference between index of sorted and unsorted position of each element and take

GCDof allabsolute differencesto find themaximumvalue ofX.

**Proof of the approach:**

The approach contains uses two things:

- Absolute differences between the index of the actual(unsorted) and sorted position of each element.
- GCD of all differences.
Let’s understand them one by one:

The idea behind absolute difference:In the above image, the first array is unsorted and the second one is in a sorted format. We can clearly see that arr[] can be sorted by swapping elements

1and6.Now, Just think about the

element: 6,which is at the first index of unsorted arr[]. Forget about rest of the elements for now. Observe that we have2 possible values of X = (1, 5)by which we can reach 6 to its sorted position.

When X = 1:

Initially unsorted arr[] = {6, 2, 3, 4, 5, 1}On swapping 6 with next X

_{th}element_{ }=_{}(2) in arr[] ={6,2, 3, 4, 5, 1}, Then arr[] will be = {2,6, 3, 4, 5, 1}

On swapping 6 with next X_{th }element = (3) in arr[] = {2,6,3, 4, 5, 1}, Then arr[] will be = {2,3,6, 4, 5, 1}

On swapping 6 with next X_{th}element = (4) in arr[] = {2, 3,6,4, 5, 1}, Then arr[] will be= {2, 3,4,6, 5, 1}

On swapping 6 with next X_{th }element = (5) in arr[] = {2, 3, 4,6,5, 1}, Then arr[] will be = {2, 3, 4,5,6, 1}

On swapping 6 with next X_{th }element = (1) in arr[] = {2, 3, 4, 5,6,1}, Then arr[] will be = {2, 3, 4, 5,1,6}

Important Note:All elements are not in their respective sorted position, As we were talking about the only element: 6, So above operations were just for element 6.

When X = 5:Initially unsorted arr[] = {6, 2, 3, 4, 5, 1}

On exchanging 6 with next Xth element = (1) in arr[] ={

6, 2, 3, 4, 5,1}, Then arr[] will be = {1, 2, 3, 4, 5,6}

We successfully put 6 to its respective sorted position in both of the cases of X. So now the question is from where we got 1 and 5 for X?

The explanation for possible values of X:Value of index, When element 6 was present in unsorted arr[] = 1(1 based indexing)

Value of index, When element 6 was present in sorted arr[] = 6(1 based indexing)

Absolute difference between sorted and unsorted index = | 6 – 1 | = 5.To cover the distance of 5 indices, We must choose the value of X in such a way that the difference should be completely divisible by X. Which conclude that

Xshould be afactorofabsolute difference.Formally, All possible values of X for a single element are = All factors of absolute difference. It can be verified that 6 can’t be placed to its respective sorted position by choosing X = {2, 3, 4}, Because none of them are factors of absolute difference=5. Therefore, for the above-discussed case, we have two possible values of X, in Which

5istheMaximum.As we know that any number is a factor in itself. Therefore we can conclude the rule:-

Suppose absolute difference = K. All possible values of X = factors(K) = {A, B, . . . . ., K}.It can be also verified that K will be the maximum among all possible factors. Formally:-

Max((factors(K)) = K = Maximum possible value of X for an element.Therefore, maximum possible value of X(Not for the final answer of the problem, just for a single element of arr[], which is 6 in this case) will be equal to the absolute difference between the index of the sorted and unsorted position of an element. Hence, the First thing of approach proves successful.

The idea behind calculating GCD of all absolute differences:For the case in the above image:-

As we can see that 6, 5, and 2 are not in their respective sorted position, Therefore:-

- Absolute difference of indices for element 6 = |2 – 6| = 4

- Max value of X for element 6 = Max(factors(4)) = Max(1, 2, 4) =
4.- Absolute difference of indices for element 5 = |3 – 5| = 2

- Max value of X for element 5 = Max(factors(2)) = Max(1, 2) =
2.- Absolute difference of indices for element 2 = |6 – 2| = 4

- Max value of X for element 2 = Max(factors(4)) = Max(1, 2, 4) =
4.These are the maximum values of X for each element, Which are not initially present in its sorted position. Now we have to find a Maximum value of X for all unsorted elements by which they should be at their sorted place(Formally, said to make arr[] sorted) under finite number of operations. For

Xshould be chosen in such a way thatit covers all the absolute differences i.e.,divisorof all the absolute differences as well as thegreatestpossible.This can be only done whenXis theGreatest Common Divisor(GCD)of all absolute differences.

Follow the steps mentioned below to implement the idea:

- Traverse through the array from i = 0 to N-1:
- Find the absolute difference of each element from their sorted position by finding the difference between (i+1) and the element [because the array contains values from 1 to N and in their sorted order
**i+1**will be in**i**index.^{th}

- Find the absolute difference of each element from their sorted position by finding the difference between (i+1) and the element [because the array contains values from 1 to N and in their sorted order
- Find the GCD of all the differences and return that as the required answer.

Below is the implementation for the above approach:

## Java

`import` `java.util.*;` `public` `class` `GFG {` ` ` `// Driver function` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Input value of N` ` ` `int` `n = ` `6` `;` ` ` `// Input arr[]` ` ` `int` `[] arr = { ` `6` `, ` `2` `, ` `3` `, ` `4` `, ` `5` `, ` `1` `};` ` ` `// Printing Maximum value of X by` ` ` `// calling MAX_X() function` ` ` `System.out.println(MAX_X(n, arr));` ` ` `}` ` ` `// Function to find maximum value of X` ` ` `static` `int` `MAX_X(` `int` `n, ` `int` `[] arr)` ` ` `{` ` ` `// Variable to Store max value of X` ` ` `int` `X = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `// Calculating GCD of` ` ` `// absolute differences` ` ` `X = GCD(Math.abs((i + ` `1` `) - arr[i]), X);` ` ` `}` ` ` `// Returning Max value of X` ` ` `// from the function.` ` ` `return` `X;` ` ` `}` ` ` `// Euclidean algorithm to return` ` ` `// GCD of two numbers` ` ` `static` `int` `GCD(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `b == ` `0` `? a : GCD(b, a % b);` ` ` `}` `}` |

## C#

`// Include namespace system` `using` `System;` `public` `class` `GFG` `{` ` ` `// Driver function` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `// Input value of N` ` ` `var` `n = 6;` ` ` ` ` `// Input arr[]` ` ` `int` `[] arr = {6, 2, 3, 4, 5, 1};` ` ` ` ` `// Printing Maximum value of X by` ` ` `// calling MAX_X() function` ` ` `Console.WriteLine(GFG.MAX_X(n, arr));` ` ` `}` ` ` `// Function to find maximum value of X` ` ` `public` `static` `int` `MAX_X(` `int` `n, ` `int` `[] arr)` ` ` `{` ` ` ` ` `// Variable to Store max value of X` ` ` `var` `X = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` ` ` `// Calculating GCD of` ` ` `// absolute differences` ` ` `X = GFG.GCD(Math.Abs((i + 1) - arr[i]), X);` ` ` `}` ` ` ` ` `// Returning Max value of X` ` ` `// from the function.` ` ` `return` `X;` ` ` `}` ` ` ` ` `// Euclidean algorithm to return` ` ` `// GCD of two numbers` ` ` `public` `static` `int` `GCD(` `int` `a, ` `int` `b)` ` ` `{` ` ` `return` `b == 0 ? a : GFG.GCD(b, a % b);` ` ` `}` `}` `// This code is contributed by aadityaburujwale.` |

**Output**

5

**Time complexity:** O(N * log(Max)), Where Max is maximum element present in arr[].**Auxiliary Space:** O(1) is, As no extra space is used.