Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
Tags
- 편스토랑 우승상품
- Git
- 데이콘
- 편스토랑
- github
- 자연어처리
- 더현대서울 맛집
- 캐치카페
- SW Expert Academy
- PYTHON
- Docker
- dacon
- leetcode
- Baekjoon
- ubuntu
- 금융문자분석경진대회
- 파이썬
- 우분투
- hackerrank
- 백준
- Kaggle
- 프로그래머스 파이썬
- Real or Not? NLP with Disaster Tweets
- AI 경진대회
- gs25
- ChatGPT
- 맥북
- 프로그래머스
- programmers
- 코로나19
Archives
- Today
- Total
솜씨좋은장씨
[leetCode] 891. Sum of Subsequence Widths (Python) 본문
728x90
반응형
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
Solution
class Solution(object):
def sumSubseqWidths(self, A):
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
'Programming > 코딩 1일 1문제' 카테고리의 다른 글
[leetCode] 136. Single Number (Python) (0) | 2020.06.13 |
---|---|
[leetCode] 412. Fizz Buzz (Python) (2) | 2020.06.13 |
[HackerRank] HackerRank in a String! (Python) (0) | 2020.06.10 |
[leetCode] 268. Missing Number (Python) (0) | 2020.06.09 |
[leetCode] 344. Reverse String (Python) (0) | 2020.06.08 |
Comments