891. Sum of Subsequence Widths
of sum Subsequence
2023-09-11 14:22:44 时间
Given an array of integers
A
, consider all non-empty subsequences ofA
.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
Approach #1: Math. [Java]
class Solution { public int sumSubseqWidths(int[] A) { int n = A.length; Arrays.sort(A); long p = 1; long mod = 1000000007; long ans = 0; for (int i = 0; i < n; ++i) { ans = (ans + (A[i] - A[n-i-1]) * p) % mod; p = (p << 1) % mod; } return (int)((ans + mod) % mod); } }
Reference:
https://zxi.mytechroad.com/blog/math/leetcode-891-sum-of-subsequence-widths/
相关文章
- Leetcode: Sum of Two Integers && Summary: Bit Manipulation
- Leetcode: Count of Range Sum
- Leetcode: Product of Array Except Self
- 404. Sum of Left Leaves
- fork failed because of Out Of Memory
- Google Earth Engine(GEE)——The bands of the specified image contains different projections
- Google Earth Engine ——ERA5-Land Monthly Averaged by Hour of Day - ECMWF Climate Reanalysis数据集
- English Voice of <<All Of Me>>
- UVa 12333 Revenge of Fibonacci (字典树+大数)
- RuntimeError: invalid argument 0: Sizes of tensors must match except in dimension 1 #805
- currval of sequence "follow_id_seq" is not yet defined in this session
- 论文阅读:Robot Learning of Everyday Object Manipulations via Human Demonstration
- 安装sql server时出现An error occurred during the installation of assembly 'microsoft.vc90.CRT'
- The Structure of an App-ios应用架构-MVC
- 解决【npm ERR! Unexpected end of JSON input while parsing near '...sh_time":141072930277'】方案
- Cadence错误之 Part xxx is out of date with respect to the design cache.
- Codeforces Round #277.5 (Div. 2)C——Given Length and Sum of Digits...
- [LeetCode] 1315. Sum of Nodes with Even-Valued Grandparent 祖父节点值为偶数的节点和
- [LeetCode] 1281. Subtract the Product and Sum of Digits of an Integer 整数的各位积和之差
- [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和
- [LintCode] Maximum Depth of Binary Tree 二叉树的最大深度
- [LeetCode] 371. Sum of Two Integers 两数之和
- [LeetCode] 363. Max Sum of Rectangle No Larger Than K 最大矩阵和不超过K
- Example of ApplicationContextAware in Spring--转
- Need a code of lazy load for div--reference
- 《YOLOv4:Optimal Speed and Accuracy of Object Detection》论文笔记
- 938. Range Sum of BST