Below is an assignment that my teacher has assigned for us. I am responsible for

Question

Below is an assignment that my teacher has assigned for us. I am responsible for telling how many swaps it would take to make an array beautiful.

What does it mean to make an array beautiful??? I do not need anyone to post this algorithm, or give me any code. I am just trying to understand what it means to make an array beautiful. This is my first seeing this.

The Assignment is below if you would like to see it:

Consider an array of n distinct integers, A = [a0, a1,...,an-1] . You can swap any two elements of the array any number of times. An array is beautiful if the sum of | ai – ai-1 | among 0 < i < n is minimal possible (after, possibly, performing some swaps).

Given the array A, find and print the minimum number of swaps that should be performed in order to make the array beautiful.

Input Format

The first line contains a single integer, n, denoting the number of elements in the array A.
The second line contains n space-separated integers describing the respective distinct values of a0, a1,...,an-1.

Constraints

• 1 n 105

• 1 ai 2x109

Output Format

Print the minimum number of swaps that should be performed in order to make the array beautiful.

Sample Input

4

2531

Sample Output

2

Explanation / Answer

Definition of a beautiful array could be different for different scenarios. But as per this scenario, a beautiful array is the array in which sum of absolute(| |) difference(| ai – ai-1 |) of adjacent elements is minimum. E.g. let n =4 then it minimizes ( | a[1] - a[0] | + |a[2] - a[1] | + |a[3] - a[2] | )

Consider given input, initially this sum is ( |5-2| + |3-5| + |1-3| ) = ( 3 + 2 + 2 ) = 7

Now possible solution is,

swap 2 & 5 => 5 2 3 1 Now sum is ( |2-5| + |3-2| + |1-3| ) = ( 3 + 1 +2 ) = 6

swap 2 & 3 => 5 3 2 1 Now sum is ( |3-5| + |2-3| + |1-2|) = (2 + 1 + 1) = 4

swap 1 & 2 => 5 3 1 2 Now sum is ( |3-5| + |1-3| + |2-1|) = (2 + 2 + 1) = 5

So the minimum sum is 4 which we got after 2 swaps. Thus the answer is 2.

If this answers your question please give thumbs up. Good Luck !!

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.