FastPrep
Problem · Array

Sum of Index-Ordered Pair Differences

Learn this problem
● MediumVisa logoVisaNEW GRADOA

Problem statement

You are given an integer array arr of length n.

For every pair of indices (i, j) such that 0 <= i < j < n, compute:

arr[j] - arr[i]

Find the sum of these differences over all valid pairs. Return the result modulo 10^9 + 7.

Complete the function sumPairDifferences, which accepts arr and returns the required result. Here, n = arr.length.

Function

sumPairDifferences(arr: int[]) → int

Examples

Example 1

arr = [1, 2, 3]return = 4

Here, n = 3. All pair differences are:

  • 2 - 1 = 1
  • 3 - 1 = 2
  • 3 - 2 = 1

The sum is 1 + 2 + 1 = 4, and 4 modulo 10^9 + 7 is 4.

Example 2

arr = [4, 1, 3, 2]return = 1000000003

Here, n = 4. All pair differences are:

  • 1 - 4 = -3
  • 3 - 4 = -1
  • 2 - 4 = -2
  • 3 - 1 = 2
  • 2 - 1 = 1
  • 2 - 3 = -1

The sum is (-3) + (-1) + (-2) + 2 + 1 + (-1) = -4, and -4 modulo 10^9 + 7 is 1000000003.

Constraints

  • 1 <= n <= 2 * 10^5
  • 0 <= arr[i] <= 10^9

More Visa problems

drafts saved locally
public int sumPairDifferences(int[] arr) {
  // write your code here
}
arr[1, 2, 3]
expected4
checking account