Consider an array of n distinct integers, A = [a 0 ,a 1 ,....,a n-1 ]. You can s
ID: 3916955 • 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 preformed to make the array beautiful.
Program to be written in Java.
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 preformed in order to make the array beautiful
Sample Input:
4
2 5 3 1
Sample Output:
2
Explanation / Answer
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Vamsi
*/
public class Beautiful_array {
public static void main(String argv[])
{
int n,i,ai=0,ai_1=0;
Scanner sc = new Scanner(System.in);//to read input
//reading array length
n =sc.nextInt();
long a[] = new long[n];//creating array
//reading array
i=0;
//reading array and...find min elements to swap
while(i<n)
{
a[i]=sc.nextInt();
if(a[ai]>a[i])
{
ai_1 = ai;
ai=i;
}
else if(a[ai_1]>a[i]||ai_1==ai)
{
ai_1 = i;
}
i++;
}
//finding number of swaps...
int s;
if(ai_1>ai)
s=ai_1-ai-1;
else
s=ai-ai_1-1;
System.out.println(s);//printing number of swaps..
}
}
output:
run:
4
2 5 3 1
2
BUILD SUCCESSFUL (total time: 5 seconds)