Сумма ширин подпоследовательностей

Источник: https://leetcode.com/problems/sum-of-subsequence-widths/

Дан массив целых чисел nums.

Для каждой непустой подпоследовательности  seq, назовем шириной разницу между минимальным и максимальным элементами подпоследовательности seq.

Вернуть сумму ширин всех подпоследовательностей массива nums. 

Поскольку ответ может быть очень большим, вернуть ответ по по модулю 109 + 7.

Пример 1:

Дано: nums = [2,1,3]
Результат: 6
Пояснение:
Подпоследовательности массива: [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
Их соответствующие ширины: 0, 0, 0, 1, 1, 2, 2.
Сумма ширин = 6.

Примечания:

• 1 <= nums.length <= 20000
• 1 <= nums[i] <= 20000

Идея решения

Исходная последовательность чисел не имеет значения, поэтому без ограничения общности мы можем отсортировать массив.

Для каждого элемента отсортированного массиваA[i]:

1. Существуют i элементов которые меньше его,
   поэтому существуют 2 ^ i подпоследовательносетй,в которых A[i] - это максимум. Поэтому мы прибавим к результату: res += A[i] * 2^i

2. Существуют такжеn - i - 1 элементов, которые больше его,
   поэтому имеем 2 ^ (n - i - 1) подпоследовательностей, в которых in which A[i] - это минимум.
   Поэтому вычтем: res -= A[i] * 2^(n - i - 1)

В переменной resу нас находится ответ.

Сложность:

Время O(NlogN)
Память O(1)  

Теория: свойства операции сравнения по модулю

 (a+b)%m = (a%m + b%m)%m

 (a-b)%m = (a%m - b%m)%m

 (ab)%m = (a%m * b%m)%m

 (a%m)%m = a%m 

 m%m=0 (остаток от делния числа на самого себя равен нулю)

Имплементация

public int sumSubseqWidths(int[] A) {
        Arrays.sort(A); // сортируем за O(N logN) 
        long c = 1, res = 0, mod = (long)1e9 + 7; // константы
// внимание, модуль можно оформить также вот так: int mod = 1_000_000_007;
// проходим по каждому элементу отсортированного массива
        for (int i = 0, n = A.length; i < n; ++i, c = c * 2 % mod)
// добавляем количество подпоследовательностей с элементами меньше A[i]
// вычитаем количество подпоследовательностей с элементами больше A[i]
// и каждый раз умножаем на 2, чтобы получить 2 в степени
            res = (res + A[i] * c - A[n - i - 1] * c) % mod;
        return (int)((res + mod) % mod);
    }

 Вопрос. Почему мы прибавляем mod перед возвращением результата?
Ответ Перед этой операцией результат может быть отрицательным. Модуль на отрицательном числе - это отрицательное число. А нам нужно получить положительное. Поэтому мы прибавляем модуль. Тогда x+mod становится подложительным.

При этом (x+mod)%mod = (x%mod + mod%mod)%mod = (x%mod + 0)%mod = x%mod для положительных чисел.