Chương trình tìm tổng hiệu tuyệt đối mọi cặp trong danh sách đã sắp xếp trong Python

Cho danh sách đã sắp xếp, tính tổng hiệu tuyệt đối giữa mọi cặp (i,j) và (j,i) đều tính. Mod 10⁹+7.

Ví dụ: → 24 (|2-4|+|2-8|+|4-2|+|4-8|+|8-2|+|8-4|).

Giải thuật (Công thức toán học O(n))

Với mảng đã sắp xếp, phần tử xuất hiện lần như số lớn hơn và lần như số nhỏ hơn.

Tổng = 2 * Σ mod M.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        m = 10**9 + 7
        total = 0
        n = len(nums)
        for i in range(n):
            total += (i * nums[i] - (n - 1 - i) * nums[i]) % m
        return (2 * total) % m

ob = Solution()
nums = [2, 4, 8]
print(ob.solve(nums))  # Output: 24

Đầu vào

[2, 4, 8]

Đầu ra

24