Given an array of integers A, consider all non-empty subsequences of A.
For any sequence S, let the width of S be the difference between the maximum and minimum element of S.
Return the sum of the widths of all subsequences of A. 
As the answer may be very large, return the answer modulo 10^9 + 7.

 
Example 1:
Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

 
Note:

1 <= A.length <= 20000
1 <= A[i] <= 20000

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Mathematics

Starter code: class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		(ret, mod, p) = (0, 10 ** 9 + 7, 1)
		for i in range(len(A)):
			ret += (A[i] - A[len(A) - i - 1]) * p % mod
			p = (p << 1) % mod
		return ret % mod


mod_ = 10 ** 9 + 7

class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		n = len(A)
		p_2 = [1]
		for i in range(1, n + 2):
			p_2.append(p_2[-1] * 2 % mod_)
		l = [0]
		for i in range(1, n):
			l.append((2 * l[-1] + (A[i] - A[i - 1]) * (p_2[i] - 1)) % mod_)
		sol = 0
		for elem in l:
			sol = (sol + elem) % mod_
		return sol


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		ret = 0
		for (i, n) in enumerate(sorted(A)):
			ret += n * pow(2, i)
			ret -= n * pow(2, len(A) - i - 1)
			ret %= 10 ** 9 + 7
		return ret


from bisect import bisect_left, bisect_right

class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		n = len(A)
		ret = 0
		A.sort()
		ret = 0
		f = {}
		for (i, x) in enumerate(A):
			if x not in f:
				f[x] = [i, i]
			else:
				f[x][1] = i
		ret = 0
		for x in f:
			(l, r) = f[x]
			sl = l
			sr = n - r - 1
			se = r - l + 1
			ret += (2 ** sl - 1) * (2 ** se - 1) * x
			ret -= (2 ** sr - 1) * (2 ** se - 1) * x
		return ret % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		N = len(A)
		A.sort()
		pow2 = [1]
		for i in range(1, N):
			pow2.append(pow2[-1] * 2 % MOD)
		ans = 0
		for (i, x) in enumerate(A):
			ans = (ans + (pow2[i] - pow2[N - 1 - i]) * x) % MOD
		return ans


class Solution:
	BASE = 10 ** 9 + 7

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		total_cnt = 0
		total_prod = 0
		ans = 0
		for num in A:
			ans = (ans + total_cnt * num - total_prod) % self.BASE
			total_cnt = (2 * total_cnt + 1) % self.BASE
			total_prod = (2 * total_prod + num) % self.BASE
		return ans


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		aa = sorted(A)
		n = len(A)
		res = 0
		md = 10 ** 9 + 7
		p2 = [1] * n
		for i in range(1, n):
			p2[i] = p2[i - 1] * 2 % md
		for i in range(n):
			res = (res + aa[i] * (p2[i] - p2[n - i - 1])) % md
		return res


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		N = len(A)
		if N == 1:
			return 0
		MOD = 10 ** 9 + 7
		A.sort()
		pow2 = [1]
		widths = 0
		for i in range(1, N):
			pow2.append(pow2[-1] * 2 % MOD)
		for i in range(N):
			widths = (widths + (pow2[i] - pow2[N - 1 - i]) * A[i]) % MOD
		return widths


from collections import deque

class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		n = len(A)
		MOD = 10 ** 9 + 7
		pows = [1] * n
		for i in range(1, n):
			pows[i] = pows[i - 1] * 2 % MOD
		A.sort()
		ans = 0
		for (i, v) in enumerate(A):
			ans += pows[i] * v - pows[n - 1 - i] * v
			ans %= MOD
		return ans % MOD


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		result = 0
		for i in range(len(A)):
			result *= 2
			result -= A[i]
			result += A[~i]
		return result % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		if len(A) == 1:
			return 0
		if len(A) == 0:
			return 0
		(ans, prev, n, mod) = (A[1] - A[0], A[1] - A[0], len(A), 1000000000.0 + 7)
		(twoPow, temp) = ([1], 2)
		for i in range(1, n):
			twoPow.append(temp + twoPow[-1])
			temp = temp * 2 % mod
		for i in range(2, len(A)):
			diff = A[i] - A[i - 1]
			prev = (2 * (prev + diff * twoPow[i - 2] % mod) % mod + diff) % mod
			ans = (ans + prev) % mod
		return int(ans)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		res = 0
		n = len(A)
		M = 10 ** 9 + 7
		c = 1
		A.sort()
		for i in range(n):
			res = (res + A[i] * c - A[n - i - 1] * c) % M
			c = (c << 1) % M
		return res


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		size = len(A)
		mod = 10 ** 9 + 7
		pow_mod = [1] * size
		for i in range(1, size):
			pow_mod[i] = pow_mod[i - 1] * 2 % mod
		A.sort()
		ans = 0
		for i in range(size):
			ans += A[i] * ((pow_mod[i] - pow_mod[size - 1 - i]) % mod) % mod
			ans %= mod
		return ans


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		res = 0
		n = len(A)
		for i in range(n):
			res += A[i] * 1 << i % 1000000007
			res -= A[i] * 1 << n - i - 1
		return res % 1000000007


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		A.sort()
		result = 0
		prev = 0
		for i in range(1, len(A)):
			d = A[i] - A[i - 1]
			prev = (2 * prev + d * (pow(2, i, MOD) - 1)) % MOD
			result = (result + prev) % MOD
		return result


class Solution:

	def sumSubseqWidths(self, A):
		return sum((((1 << i) - (1 << len(A) - i - 1)) * a for (i, a) in enumerate(sorted(A)))) % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		B = sorted(A)
		res = 0
		mod = 10 ** 9 + 7
		for i in range(len(B)):
			res += B[i] * ((1 << i) - (1 << len(B) - i - 1))
		return res % mod


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		if not A:
			return 0
		ans = 0
		A.sort()
		for (i, n) in enumerate(A):
			ans += ((1 << i) - (1 << len(A) - i - 1)) * n
		return ans % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		return sum(((1 << i) * num - (1 << len(A) - i - 1) * num for (i, num) in enumerate(sorted(A)))) % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		A.sort()
		n = len(A)
		return sum((a * ((1 << i) - (1 << n - i - 1)) for (i, a) in enumerate(A))) % mod


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		LIM = 10 ** 9 + 7
		res = 0
		powTable = [1]
		for _ in range(len(A)):
			powTable.append(2 * powTable[-1] % LIM)
		for (i, val) in enumerate(A):
			res = (res + val * powTable[i] - val * powTable[len(A) - i - 1]) % LIM
		return res


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		total = 0
		MOD = 10 ** 9 + 7
		powerSum = 2 ** 0
		counter = 2
		currSum = A[0]
		for i in range(1, len(A)):
			total += powerSum * A[i] - currSum
			currSum *= 2
			currSum += A[i]
			powerSum += counter
			counter *= 2
		return total % MOD


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		S = 0
		B = [1] * len(A)
		for i in range(1, len(B)):
			B[i] = 2 * B[i - 1]
		for i in range(len(A)):
			S += (B[i] - B[-1 - i]) * A[i]
		return S % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, a: List[int]) -> int:
		a.sort()
		print(a)
		count = 0
		n = 1
		c = a[0]
		for (m, i) in enumerate(a[1:]):
			n *= 2
			count += (n - 1) * i - c
			c = c * 2 + i
		return count % (pow(10, 9) + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		l = len(A)
		p = [1]
		ans = 0
		for i in range(1, l):
			p.append(p[-1] * 2)
		for (i, j) in enumerate(A):
			ans += (p[i] - p[l - i - 1]) * j
		return ans % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		n = len(A)
		total = 0
		for i in range(n):
			a = A[i]
			left = i
			right = n - i - 1
			total += ((1 << left) - 1) * a
			total -= ((1 << right) - 1) * a
		return total % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, nums):
		res = 0
		for (i, num) in enumerate(sorted(nums)):
			res += ((1 << i) - (1 << len(nums) - i - 1)) * num
		return res % 1000000007


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A = sorted(A)
		r = 0
		m = 10 ** 9 + 7
		for i in range(len(A) - 1):
			r += (A[i + 1] - A[i]) * ((1 << len(A)) - (1 << i + 1) - (1 << len(A) - i - 1) + 1)
		r %= m
		return r


from bisect import bisect_left, bisect_right

class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		n = len(A)
		ret = 0
		A.sort()
		MOD = 10 ** 9 + 7

		@lru_cache
		def bimod(n):
			if n == 0:
				return 1
			di = bimod(n // 2)
			if n % 2 == 0:
				return di * di % MOD
			return di * di * 2 % MOD

		@lru_cache
		def nonempty(n):
			return bimod(n) - 1
		i = 0
		while i < n:
			j = i
			while j < n and A[j] == A[i]:
				j += 1
			se = j - i
			sl = i
			sr = n - j
			ret = (ret + A[i] * nonempty(se) * (nonempty(sl) - nonempty(sr)) % MOD) % MOD
			i = j
		return ret % MOD


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A = sorted(A)
		(total, cur, cnt) = (0, 0, 0)
		MOD = 10 ** 9 + 7
		for i in range(1, len(A)):
			cnt *= 2
			cnt += 1
			cur *= 2
			cur += (A[i] - A[i - 1]) * cnt
			cur %= MOD
			total += cur
			total %= MOD
		return total


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A = sorted(A)
		res = 0
		MOD = 10 ** 9 + 7
		c = 1
		for i in range(len(A)):
			res = (res + A[i] * c % MOD) % MOD
			c <<= 1
			c %= MOD
		c = 1
		for i in range(len(A) - 1, -1, -1):
			res = (res - A[i] * c % MOD) % MOD
			c <<= 1
			c %= MOD
		return (res + MOD) % MOD


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		POW2 = [1 << i for i in range(len(A))]
		return sum(((POW2[i] - POW2[len(A) - 1 - i]) * n for (i, n) in enumerate(sorted(A)))) % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		n = len(A)
		A.sort()
		B = [A[i] - A[n - i - 1] for i in range(n)]
		ans = 0
		for (i, v) in enumerate(B):
			ans = (ans + (v << i)) % mod
		return ans


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		res = 0
		mod = 10 ** 9 + 7
		N = len(A)
		for i in range(len(A)):
			res += ((1 << i) - (1 << N - i - 1)) * A[i] % mod
		return res % mod


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		N = len(A)
		A = sorted(A)
		MODS = 10 ** 9 + 7
		(pow2, res) = ([1], 0)
		for ii in range(1, N):
			pow2.append(2 * pow2[-1] % MODS)
		for (ii, jj) in enumerate(A):
			res = (res + (pow2[ii] - pow2[N - ii - 1]) * jj) % MODS
		return res


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		A.sort()
		n = len(A)
		ans = 0

		def exp(n):
			res = 1
			x = 2
			while n:
				if n & 1:
					res = res * x % mod
				n = n >> 1
				x = x * x % mod
			return res
		for i in range(n):
			ans = (ans + exp(i) * A[i] - exp(n - i - 1) * A[i] + mod) % mod
		return ans


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		mod = 10 ** 9 + 7
		n = len(A)
		if n == 1:
			return 0
		pow = [1]
		for i in range(1, n):
			pow.append(pow[-1] * 2 % mod)
		A = sorted(A)
		s = 0
		for (i, elem) in enumerate(A):
			(n_max, n_min) = (i, n - i - 1)
			N1 = pow[i]
			N2 = pow[n - i - 1]
			s += elem * (N1 - N2) % (10 ** 9 + 7)
			s = s % (10 ** 9 + 7)
		return s


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		MOD = 10 ** 9 + 7
		A = sorted(A)
		if len(A) == 1:
			return 0
		lastaddon = 0
		lastv = 0
		for i in range(1, len(A)):
			lastaddon = 2 * lastaddon + (2 ** i - 1) * (A[i] - A[i - 1])
			lastv += lastaddon
		return lastv % MOD


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		n = len(A)
		widthsum = 0
		mod = 10 ** 9 + 7
		A.sort()
		p = s = 0
		(pre, suf) = ([], [])
		for i in range(n):
			p += A[i]
			s += A[-i - 1]
			pre.append(p)
			suf.append(s)
		for l in range(n):
			widthsum += 2 ** l * (suf[l] - pre[l])
			widthsum %= mod
		return widthsum


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		N = len(A)
		return sum((num * (2 ** i - 2 ** (N - i - 1)) for (i, num) in enumerate(A))) % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		Mod = 1000000000.0 + 7
		n = len(A)
		twoPower = [1]
		while len(twoPower) < n:
			twoPower.append(twoPower[len(twoPower) - 1] * 2 % Mod)
		A.sort()
		ans = 0
		for (i, a) in enumerate(A):
			left = i
			right = n - i - 1
			ans = (ans + (twoPower[left] - twoPower[right]) * a) % Mod
		return int((ans + Mod) % Mod)


class Solution:

	def sumSubseqWidths(self, A: List[int], recursed=False) -> int:
		return sum((x * (2 ** i - 2 ** (len(A) - i - 1)) for (i, x) in enumerate(sorted(A)))) % (int(1000000000.0) + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A = sorted(A)
		length = len(A)
		_sum = 0
		for i in range(length):
			_sum += A[i] * 2 ** i
		for i in range(length):
			_sum -= A[i] * 2 ** (length - i - 1)
		return _sum % (10 ** 9 + 7)


class Solution:

	def sumSubseqWidths(self, A: List[int]) -> int:
		A.sort()
		total = 0
		const = 10 ** 9 + 7
		for i in range(len(A)):
			total += 2 ** i * A[i] - 2 ** (len(A) - i - 1) * A[i]
			total = total % const
		return total