Maximize X such that Array could be sorted by swapping components X distance aside


Given an enter arr[] of size N, Which comprises integers from 1 to N in unsorted order. You possibly can apply just one kind of operation on arr[] components’:

Then the duty is to seek out the utmost worth of X by which all the weather must be at their respective place of sorted order.

Enter: N = 6, arr[] = {6, 2, 3, 4, 5, 1} 
Output: 5
Rationalization: arr[] could be sorted by exchanging components at first (A1 = 6) 
and final(A6 = 1) index of arr[]. Right here worth of X is 5 and in addition follows the rule of given operation. 
It may be verified that there’s no max worth relatively that 5 of  by which arr[] could be sorted.

Enter: N = 6, arr[] = {3, 2, 1, 6, 5, 4}
Output: 2
Rationalization: Aspect at 1st and threerd  index could be swapped 
to type the arr[] as = {1, 2, 3, 6, 5, 4} after which 4th  and 6th 
factor could be exchanged with one another to make arr[] sorted: {1, 2, 3, 4, 5, 6}.
For first operation worth of X used : 2
For second operation worth of X used : 2
Then, Most worth of X amongst all operations by which 
we are able to place all components to their respective sorted place: 2

The strategy comprises makes use of two issues:

  • Absolute variations between the index of the particular(unsorted) and sorted place of every factor. 
  • GCD of all variations.

Let’s perceive them one after the other:

  • The thought behind absolute distinction:

Sorting arr[] by exchanging 6 with 1

Within the above picture, the primary array is unsorted and the second is in a sorted format. We will clearly see that arr[] could be sorted by swapping components 1 and 6.

Now, Simply take into consideration the factor: 6, which is on the first index of unsorted arr[]. Overlook about remainder of the weather for now. Observe that now we have 2 doable values of X = (1, 5)  by which we are able to attain 6 to its sorted place. 

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

On swapping 6 with subsequent Xth factor  = (2) in arr[] ={6, 2, 3, 4, 5, 1}, Then arr[] might be  = {2, 6, 3, 4, 5, 1}
On swapping 6 with subsequent Xth  factor = (3) in arr[] = {2, 6, 3, 4, 5, 1}, Then arr[] might be  = {2, 3, 6, 4, 5, 1}
On swapping 6 with subsequent Xth factor = (4) in arr[] = {2, 3, 6, 4, 5, 1}, Then arr[] might be= {2, 3, 4, 6, 5, 1}
On swapping 6 with subsequent Xth factor = (5) in arr[] = {2, 3, 4, 6, 5, 1}, Then arr[] might be = {2, 3, 4, 5, 6, 1}
On swapping 6 with subsequent Xth factor = (1) in arr[] = {2, 3, 4, 5, 6, 1}, Then arr[] might be = {2, 3, 4, 5, 1, 6}

Illustration of the process when X = 1

Illustration of the method when X = 1

Essential Be aware: All components should not of their respective sorted place, As we had been speaking about the one factor: 6, So above operations had been only for factor 6.  

When X = 5:  

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

On exchanging 6 with subsequent Xth factor  = (1) in arr[] ={6, 2, 3, 4, 5, 1}, Then arr[] might be  = {1, 2, 3, 4, 5, 6}
We efficiently put 6 to its respective sorted place in each of the instances of X. So now the query is from the place we received 1 and 5 for X?

The reason for doable values of X:

Worth of index, When factor 6 was current in unsorted arr[] = 1(1 based mostly indexing)
Worth of index, When factor 6 was current in sorted arr[] = 6(1 based mostly indexing)
Absolute distinction between sorted and unsorted index = | 6 – 1 | = 5.

Illustration for the case of x = 5

Illustration for the case of x = 5

To cowl the gap of 5 indices, We should select the worth of X in such a means that the distinction must be fully divisible by X. Which conclude that X must be a issue of absolute distinction

Formally, All doable values of X for a single factor are = All elements of absolute distinction. It may be verified that 6 can’t be positioned to its respective sorted place by selecting X = {2, 3, 4}, As a result of none of them are elements of absolute distinction=5. Subsequently, for the above-discussed case, now we have two doable values of X, in Which 5 is the Most.

As we all know that any quantity is a think about itself. Subsequently we are able to conclude the rule:-

Suppose absolute distinction = Okay. All doable values of X  = elements(Okay) = {A, B, . . . . ., Okay}.It may be additionally verified that Okay would be the most amongst all doable elements. Formally:-

Max((elements(Okay)) = Okay = Most doable worth of X for a component.

Subsequently, most doable worth of X(Not for the ultimate reply of the issue, only for a single factor of arr[], which is 6 on this case) might be equal to absolutely the distinction between the index of the sorted and unsorted place of a component. Therefore, the Very first thing of strategy proves profitable. 

  • The thought behind calculating GCD of all absolute variations:
Unsorted and sorted array with indices

Unsorted and sorted array with indices

For the case within the above picture:-

As we are able to see that 6, 5, and a pair of should not of their respective sorted place, Subsequently:-

  • Absolute distinction of indices for factor 6 = |2 – 6| = 4
    • Max worth of X for factor 6 = Max(elements(4)) = Max(1, 2, 4) =  4.
  • Absolute distinction of indices for factor 5 = |3 – 5| = 2
    • Max worth of X for factor 5 = Max(elements(2)) = Max(1, 2) = 2.
  • Absolute distinction of indices for factor 2 = |6 – 2| = 4
    • Max worth of X for factor 2 = Max(elements(4)) = Max(1, 2, 4) = 4.

These are the utmost values of X for every factor, Which aren’t initially current in its sorted place. Now now we have to discover a  Most worth of X for all unsorted components by which they need to be at their sorted place(Formally, stated to make arr[] sorted) underneath finite variety of operations. For X must be chosen in such a means that it covers all absolutely the variations i.e., divisor of all absolutely the variations in addition to the biggest doable. This may be solely finished when X is the Biggest Widespread Divisor(GCD) of all absolute variations.

Time complexity: O(N * log(Max)), The place Max is most factor current in arr[].
Auxiliary Area: O(1) is, As no further area is used.

Leave a Reply