Problem:
Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j ], then the
pair (i,j) is called an inversion of A.
List the inversions for the given array.
Solution:
package com.basics;
import java.util.Scanner;
public class InversionsOfAnArray {
static int[] array;
int arrayLimit;
public static void main(String[] args) {
InversionsOfAnArray inversionsOfAnArray = new InversionsOfAnArray();
inversionsOfAnArray.initializeTheArrays();
inversionsOfAnArray.findInversions();
}
public void initializeTheArrays(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter the array limit");
arrayLimit = scanner.nextInt();
array = new int[arrayLimit];
System.out.println("enter the array elements");
for (int i = 0; i < array.length; i++) {
System.out.println("enter the element");
array[i] = scanner.nextInt();
}
scanner.close();
}
public void findInversions(){
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if(array[i] > array[j]){
System.out.println("The inversion Pair is: " + array[i] + " ," + array[j]);
}
}
}
}
}
Output:
enter the array limit
5
enter the array elements
enter the element
2
enter the element
3
enter the element
8
enter the element
6
enter the element
1
The inversion Pair is: 2 ,1
The inversion Pair is: 3 ,1
The inversion Pair is: 8 ,6
The inversion Pair is: 8 ,1
The inversion Pair is: 6 ,1
Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j ], then the
pair (i,j) is called an inversion of A.
List the inversions for the given array.
Solution:
package com.basics;
import java.util.Scanner;
public class InversionsOfAnArray {
static int[] array;
int arrayLimit;
public static void main(String[] args) {
InversionsOfAnArray inversionsOfAnArray = new InversionsOfAnArray();
inversionsOfAnArray.initializeTheArrays();
inversionsOfAnArray.findInversions();
}
public void initializeTheArrays(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter the array limit");
arrayLimit = scanner.nextInt();
array = new int[arrayLimit];
System.out.println("enter the array elements");
for (int i = 0; i < array.length; i++) {
System.out.println("enter the element");
array[i] = scanner.nextInt();
}
scanner.close();
}
public void findInversions(){
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if(array[i] > array[j]){
System.out.println("The inversion Pair is: " + array[i] + " ," + array[j]);
}
}
}
}
}
Output:
enter the array limit
5
enter the array elements
enter the element
2
enter the element
3
enter the element
8
enter the element
6
enter the element
1
The inversion Pair is: 2 ,1
The inversion Pair is: 3 ,1
The inversion Pair is: 8 ,6
The inversion Pair is: 8 ,1
The inversion Pair is: 6 ,1
Please change the SOP statement in findInversions() to System.out.println("The inversion Pair is: " + i + " ," + j);
ReplyDeleteIn the problem statement it is mentioned that i, j as the pair, not A[i] and A[j] as the pair