l; while(i
For this problem I have a java code:
import java.util.Arrays; import java.util.Scanner; public class MergeSortWeightedSumInversion { public static long merge(int arr[], int l, int mid, int r) { long weight = 0; int n1 = mid-l+1; int n2 = r-mid; int[] a = new int[n1]; int[] b = new int[n2]; for(int i = 0; i < n1; i++) { a[i] = arr[l+i]; } for(int i = 0; i < n2; i++) { b[i] = arr[mid+i+1]; } int i = 0, j = 0, k = l; while(i<n1 && j<n2) { if(a[i] <= b[j]) { arr[k] = a[i]; k++; i++; } else { weight += (a[i] + b[j]); arr[k] = b[j]; k++; j++; } } while(i<n1) { arr[k] = a[i]; k++; i++; } while(j<n2) { arr[k] = b[j]; k++; j++; } return weight; } public static long mergeSort(int arr[], int l, int r) { long weight = 0; if(l < r) { int mid = (l+r)/2; weight += mergeSort(arr, l, mid); weight += mergeSort(arr,mid+1,r); weight += merge(arr,l,mid,r); } return weight; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n; n = scan.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = scan.nextInt(); } System.out.println(mergeSort(arr, 0, n-1)); } } This is wrong because I tried testing it on the array: [7,3,8,1,5] and I got a weight of 26, its only adding up half of the inversions. How would I modify it so that it works? Code in java and time complexity must be O(n log(n)) please.
![In the problem of counting inversions, you are given a permutation a₁, a2..., an of numbers
1,2,...,n, and the goal is to count the number of pairs i, j, where i < j and ai > aj. In
this homework problem, you are given a sequence of n numbers b₁,b2,..., bn and your task
is to compute the "weighted count" of inversions defined as follows: An inversion is a pair
of indices i, j where i <j and bi > bj. An i, j inversion has weight b; + b; and the weighted
count for the input sequence is the sum of the weights of all its inversions.
For example, for n = 5 and input sequence 7, 3, 8, 1, 5, we have the following inversions
weights: 7+3= 10, 7+1 = 8, 7+5 = 12, 3+1=4, 8+1=9, and 8+5 = 13. The overall
weighted count is: 10+ 8 + 12 +4+9+13= 56.
Design an O(n log n) algorithm which computes the weighted count of inversions for a
given input sequence.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fdad64e64-bab8-4c8e-9af1-b3316be12760%2Fb7623895-bbbc-4331-9f2c-ccfd472e0475%2Fe2yrbpi_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Step by step
Solved in 3 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)