Consider an array of n distinct integers, A = [a 0 , a 1 ,…, a n-1 ] . You can s
ID: 3917140 • Letter: C
Question
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 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
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.
(write on eclipse)
Explanation / Answer
import java.util.*;
public class MinSwaps {
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void reverse(int[] arr) {
int size = arr.length;
for (int i=0; i<size/2; i++) {
swap(arr,i,size-i-1);
}
}
private static int minSwapsRequired(int[] arr, int size, int[] sortedArray) {
int answer = 0;
Map<Integer, Integer> value2indexconvertion = new HashMap<Integer, Integer>();
for (int i = 0; i < size; i++) {
value2indexconvertion.put(arr[i], i);
}
for (int i = 0; i < size; i++) {
if (arr[i] != sortedArray[i]) {
// At index i there must be value sortedArray[i]
// Find the position of value sortedArray[i] in the input array
int position = value2indexconvertion.get(sortedArray[i]);
// Swap sortedArray[i] with arr[i]
swap(arr, i, position);
// Update the position of arr[position] in the value2indexconvertion map
value2indexconvertion.put(arr[position], position);
// Increment swap count
answer++;
}
}
return answer;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
//taking no of elements input from the user
int size = scanner.nextInt();
//taking elements from the user
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = scanner.nextInt();
}
//copying the array to sortedarry array and then sort
int[] sortedArray = Arrays.copyOf(arr, arr.length);
Arrays.sort(sortedArray);
//passing that sortedarray
int answer = minSwapsRequired(Arrays.copyOf(arr, arr.length), size, sortedArray);
reverse(sortedArray);
int ansR = minSwapsRequired(arr, size, sortedArray);
//printing the result
System.out.println(Math.min(answer,ansR));
}
}