Assignment # 4 Due Tuesday, October 31st 2017, 11.59 pm Consider an array of n d

Question

Assignment # 4
Due Tuesday, October 31st 2017, 11.59 pm
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 2 * 109
Output Format
Print the minimum number of swaps that should be performed in order to make the array beautiful.
Sample Input
4
2 5 3 1
Sample Output
2
Explanation
Let's define array B = [1,2,3,5] to be the beautiful reordering of array A, as the sum of the absolute values of differences between its adjacent elements is minimal among all permutations and only two swaps (1 with 2 and then 2 with 5 ) was performed.

Explanation / Answer

Any array to give minimal sum of |ai - a(i-1)| is to be in some sorted order.

As in sorted array, ai is nearest to a(i-1).

Here what we need is to find the minimum number to swaps to make an array sorted.

Below is the interactive program written in Java to implement the logic with console output at the end.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ArrayBeautify {
   private int arr[];
   private int swapCount;
  
   ArrayBeautify(int a[]){
       arr=a;
       swapCount=0;
   }
  
   void swap(int i,int j){ //to perform swap operation and count number of swaps.
       int temp = arr[i];
       arr[i]=arr[j];
       arr[j]=temp;
       swapCount++;
   }
  
   boolean isBeautiful(){               //to check if array is Beautiful
       int check = 0;
       for(int i=0; i<arr.length-1;i++){
           if(arr[i]>arr[i+1])
               check = 1;
       }
       if(check == 1)
           return false;
       else
           return true;
   }
  
   int min(int j){                       //to check the index of minimum value in subarray a[j]-a[n]
       int min=arr[j];
       int k=j;
       for(int i=j+1;i<arr.length;i++)
           if(arr[i]<min){
               min=arr[i];
               k=i;}
       return k;
   }
  
   void beautify(){              
       for(int i=0;i<arr.length;i++){
           if(isBeautiful())
               break;
           int m=min(i);
           if(m>i)
               swap(i,m);
       }
   }
  
   public static void main(String args[])throws IOException{
       InputStreamReader o=new InputStreamReader(System.in);
       BufferedReader ob=new BufferedReader(o);
       System.out.println("Enter Number of elements in the array");
       int n = Integer.parseInt(ob.readLine());
       int a[] = new int[n];
       for(int i=0;i<n;i++){
           System.out.println("Enter "+(i+1)+" element of array");
           a[i]=Integer.parseInt(ob.readLine());
       }
       ArrayBeautify b = new ArrayBeautify(a);
       b.beautify();
       System.out.println("Number of swaps required to make this array beautiful: "+b.swapCount);
   }
}

Console:

Enter Number of elements in the array
4
Enter 1 element of array
2
Enter 2 element of array
5
Enter 3 element of array
3
Enter 4 element of array
1
Number of swaps required to make this array beautiful: 2

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects