Участник:Alvant/TaskSumOfSubsequenceWidths

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/sum-of-subsequence-widths

from typing import List
 
class Solution:
    MODULO = 10 ** 9 + 7
    powers_of_two = dict()
 
    def sumSubseqWidths(self, A: List[int]) -> int:
        sorted_list = sorted(A)
        num_elements = len(sorted_list)
 
        self.compute_powers_of_two(len(sorted_list))
 
        result = 0
 
        for index, element in enumerate(sorted_list):
            num_times_acts_as_upper_bound = index
            num_times_acts_as_lower_bound = len(sorted_list) - 1 - index
 
            addition = 0
 
            addition = addition + self.powers_of_two[num_times_acts_as_upper_bound] * element
            addition %= self.MODULO
 
            addition = addition - self.powers_of_two[num_times_acts_as_lower_bound] * element
            addition %= self.MODULO
 
            result = result + addition
            result %= self.MODULO
 
        return result
 
    def compute_powers_of_two(self, max_power: int) -> None:
        self.powers_of_two[0] = 1
 
        for power in range(1, max_power + 1):
            self.powers_of_two[power] = (2 * self.powers_of_two[power - 1]) % self.MODULO