Problem

You are given an integer array nums and a positive integer k. Return the sum of the maximum and minimum elements of all subsequences of nums with at most k elements.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input: nums = [1,2,3], k = 2
Output: 24
Explanation:
The subsequences of `nums` with at most 2 elements are:
**Subsequence** | Minimum | Maximum | Sum  
---|---|---|---  
`[1]` | 1 | 1 | 2  
`[2]` | 2 | 2 | 4  
`[3]` | 3 | 3 | 6  
`[1, 2]` | 1 | 2 | 3  
`[1, 3]` | 1 | 3 | 4  
`[2, 3]` | 2 | 3 | 5  
**Final Total** |   |   | 24  
The output would be 24.

Example 2

1
2
3
4
5

Input: nums = [5,0,6], k = 1
Output: 22
Explanation:
For subsequences with exactly 1 element, the minimum and maximum values are
the element itself. Therefore, the total is `5 + 5 + 0 + 0 + 6 + 6 = 22`.

Example 3

1
2
3
4
5

Input: nums = [1,1,1], k = 2
Output: 12
Explanation:
The subsequences `[1, 1]` and `[1]` each appear 3 times. For all of them, the
minimum and maximum are both 1. Thus, the total is 12.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= min(70, nums.length)

Examples

Solution

Method 1 – Combinatorics + Sorting + Fast Exponentiation

Intuition

For each element, count how many subsequences of size up to k have it as the minimum or maximum. If the array is sorted, for each index, the number of ways to pick elements to the left and right (up to k-1) gives the count. Use combinatorics and fast exponentiation to efficiently compute the sum for all possible subsequence sizes.

Approach

  1. Sort the array.
  2. Precompute powers of 2 up to n for fast combinatorial calculations.
  3. For each index, for all sizes up to k, count how many subsequences have nums[i] as min or max using binomial coefficients.
  4. For each index, add (count as max - count as min) * nums[i] to the answer.
  5. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int sumOfMaxAndMin(vector<int>& nums, int k) {
        const int MOD = 1e9+7;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<long long> pow2(n+1, 1);
        for (int i = 1; i <= n; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            int left = min(i, k-1);
            int right = min(n-i-1, k-1);
            long long cnt_max = pow2[i] - 1;
            long long cnt_min = pow2[n-i-1] - 1;
            for (int sz = 1; sz <= k; ++sz) {
                if (i >= sz-1) cnt_max = (cnt_max + 1) % MOD;
                if (n-i-1 >= sz-1) cnt_min = (cnt_min + 1) % MOD;
            }
            ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i]) % MOD;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func sumOfMaxAndMin(nums []int, k int) int {
    const MOD = 1_000_000_007
    n := len(nums)
    sort.Ints(nums)
    pow2 := make([]int, n+1)
    pow2[0] = 1
    for i := 1; i <= n; i++ {
        pow2[i] = pow2[i-1] * 2 % MOD
    }
    ans := 0
    for i := 0; i < n; i++ {
        cnt_max := pow2[i]
        cnt_min := pow2[n-i-1]
        ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i] % MOD) % MOD
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int sumOfMaxAndMin(int[] nums, int k) {
        int MOD = 1_000_000_007, n = nums.length;
        Arrays.sort(nums);
        long[] pow2 = new long[n+1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) pow2[i] = pow2[i-1] * 2 % MOD;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long cnt_max = pow2[i];
            long cnt_min = pow2[n-i-1];
            ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i] % MOD) % MOD;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun sumOfMaxAndMin(nums: IntArray, k: Int): Int {
        val MOD = 1_000_000_007
        val n = nums.size
        nums.sort()
        val pow2 = LongArray(n+1) { 1L }
        for (i in 1..n) pow2[i] = pow2[i-1] * 2 % MOD
        var ans = 0L
        for (i in 0 until n) {
            val cnt_max = pow2[i]
            val cnt_min = pow2[n-i-1]
            ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i] % MOD) % MOD
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def sumOfMaxAndMin(self, nums: list[int], k: int) -> int:
        MOD = 10**9+7
        n = len(nums)
        nums.sort()
        pow2 = [1]*(n+1)
        for i in range(1, n+1):
            pow2[i] = pow2[i-1]*2 % MOD
        ans = 0
        for i in range(n):
            cnt_max = pow2[i]
            cnt_min = pow2[n-i-1]
            ans = (ans + (cnt_max - cnt_min) * nums[i]) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn sum_of_max_and_min(nums: Vec<i32>, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut nums = nums;
        nums.sort();
        let n = nums.len();
        let mut pow2 = vec![1i64; n+1];
        for i in 1..=n {
            pow2[i] = pow2[i-1] * 2 % MOD;
        }
        let mut ans = 0i64;
        for i in 0..n {
            let cnt_max = pow2[i];
            let cnt_min = pow2[n-i-1];
            ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i] as i64 % MOD) % MOD;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    sumOfMaxAndMin(nums: number[], k: number): number {
        const MOD = 1e9+7;
        nums.sort((a, b) => a - b);
        const n = nums.length;
        const pow2 = Array(n+1).fill(1);
        for (let i = 1; i <= n; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            const cnt_max = pow2[i];
            const cnt_min = pow2[n-i-1];
            ans = (ans + (cnt_max - cnt_min + MOD) % MOD * nums[i] % MOD) % MOD;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting and precomputing powers.
  • 🧺 Space complexity: O(n), for the powers array.