Skip to content
Related Articles

Related Articles

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

View Discussion
Improve Article
Save Article
  • Last Updated :30 Sep, 2022
View Discussion
Improve Article
Save Article

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 Ai 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: 5
Explanation: arr[] can be sorted by exchanging elements at first (A1 = 6) 
and last(A6 = 1) index of arr[]. Here value of X is 5 and also follows the rule of given operation. 
It can be verified that there is no max value rather that 5 of  by which arr[] can be sorted.

Input: N = 6, arr[] = {3, 2, 1, 6, 5, 4}
Output: 2
Explanation: Element at 1st and 3rd  index can be swapped 
to form the arr[] as = {1, 2, 3, 6, 5, 4} and then 4th  and 6th 
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 GCD of all absolute differences to find the maximum value of X.

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:

Sorting arr[] by exchanging 6 with 1

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 1 and 6.

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 have 2 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 Xth 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 Xth  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 Xth 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 Xth 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 Xth element = (1) in arr[] = {2, 3, 4, 5, 6, 1}, Then arr[] will be = {2, 3, 4, 5, 1, 6}

Illustration of the process when X = 1

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.

Illustration for the case of x = 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 X should be a factor of absolute 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 5 isthe Maximum.

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:

Unsorted and sorted array with indices

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 X should be chosen in such a way thatit covers all the absolute differences i.e., divisor of all the absolute differences as well as the greatest possible. This can be only done when X is the Greatest 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 ith index.
  • Find the GCD of all the differences and return that as the required answer.

Below is the implementation for the above approach:

Java




importjava.util.*;
publicclassGFG {
 
    // Driver function
    publicstaticvoidmain(String[] args)
    {
        // Input value of N
        intn = 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
    staticintMAX_X(intn, int[] arr)
    {
 
        // Variable to Store max value of X
        intX = 0;
        for(inti = 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.
        returnX;
    }
 
    // Euclidean algorithm to return
    // GCD of two numbers
    staticintGCD(inta, intb)
    {
        returnb == 0? a : GCD(b, a % b);
    }
}

C#




// Include namespace system
usingSystem;
 
 
publicclassGFG
{
    // Driver function
    publicstaticvoidMain(String[] args)
    {
        // Input value of N
        varn = 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
    publicstaticintMAX_X(intn, int[] arr)
    {
       
        // Variable to Store max value of X
        varX = 0;
        for(inti = 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.
        returnX;
    }
   
    // Euclidean algorithm to return
    // GCD of two numbers
    publicstaticintGCD(inta, intb)
    {
        returnb == 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.


My Personal Notesarrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!