Rearrange the given Array to make it sorted and GCD of components until i is Ok

We’ve got to know the next two issues:

1. By which case of L and R association is feasible.
2. Association of components.

Let’s talk about them one after the other.

• To Examine association is feasible or not:-

 Let’s take an random instance arr[] = {3, 1, 2}, Then all attainable preparations of arr[] are:

First association: arr[] = {1, 2, 3} 

GCD₀ = GCD(1) = 1
GCD₁ = GCD(1, 2)= 1
GCD₂ = GCD(1, 2, 3) = 1  

Whole sum of GCD = 1 + 1 + 1 = 3 

Second association: arr[] = {1, 3, 2}  

Whole sum of GCD = 1 + 1 + 1 = 3 

Third association: arr[] = {2, 1, 3}  

Whole sum of GCD = 2 + 1 + 1 = 4

 Fourth association: arr[] = {2, 3, 1}  

Whole sum of GCD = 2 + 1 + 1 = 4

Fifth association: arr[] = {3, 1, 2}  

Whole sum of GCD = 3 + 1 + 1 = 5

Sixth association: arr[] = {3, 2, 1}  

Whole sum of GCD = 3 + 1 + 1 = 5 

For all above association we are able to conclude that the Minimal worth and Most worth of whole sum of GCD is the same as 3 and 5 respectively. This provides us concept that association is feasible when R lies within the vary of [L, L+1.., 2*L-1]. In above preparations L = 3 and Max and min worth of Ok is 3(equal to L) and 5(equal to 2 * L – 1) respectively.

• Now Association of components (excluding circumstances during which association isn’t attainable):

1. From above preparations we are able to conclude that when Ok = L, Then, It may be verified that printing counting from 1 to L will give the whole sum of GCD equal to Ok for all legitimate values of L and R.
2. For remainder of the circumstances(When L != R), Take first_element as ((Ok % L) + 1) and print it. Then print remainder of the weather from 1 to L excluding first_element(to keep away from duplicate, as a result of we now have printed it at beginning of association). See examples under for readability:

Instance 1: arr[] = {2, 3, 4, 1, 5}, Ok = 5

L = 5, Ok = 5, we are able to clearly see that L is the same as R,  Then print counting from 1 to L:

New association = {1, 2, 3, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 1 + 1 + 1 + 1 + 1 = 5, Whole sum of GCD is the same as Ok, Therefore association glad in addition to in sorted format from index 1 to N – 1.

Instance 2: arr[] = {2, 3, 4, 1, 5}, Ok = 7

L = 5, Ok = 7, we are able to clearly see that L isn’t equal to R, Then first_element = ((Ok % L) + 1) = ((7 % 5) + 1) = 2 + 1 = 3.

Now print first_element at first index of association and then counting from 1 to L excluding first_element

New association = {3, 1, 2, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 3 + 1 + 1 + 1 + 1 = 7, Whole sum of GCD is the same as Ok, Therefore association glad in addition to in sorted format from index 1 to N – 1.