Sponsored
Sponsored
This approach involves sorting the array first. For each element in the sorted array, think of it appearing as the largest and smallest element in various subsequences. Using powers of two, we can determine the number of times an element appears as a maximum or minimum. This reduces the problem to simple arithmetic operations, making the solution efficient enough to handle large input sizes. The final result is calculated using modulo 10^9 + 7.
Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int sumSubseqWidths(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 long mod = 1e9 + 7, x = 0, n = nums.size(), pow2 = 1;
10 vector<long> pow2Arr(n, 1);
11 for (int i = 1; i < n; ++i)
12 pow2Arr[i] = (pow2Arr[i - 1] * 2) % mod;
13 for (int i = 0; i < n; ++i) {
14 x = (x + nums[i] * (pow2Arr[i] - pow2Arr[n - 1 - i])) % mod;
15 }
16 return (int)x;
17 }
18};In C++, we sort the input array to arrange each element by its relative value. We then precompute powers of two modulo 10^9 + 7 to simplify the process of calculating the resulting sum. By iterating through the sorted numbers, we determine each number's influence as a maximum and a minimum across all possible subsequences, accumulating these effects to get the final result.