3714. Maximum And Minimum Sums Of At Most Size K Subsequences¶

Difficulty: Medium

3714. Maximum and Minimum Sums of at Most Size K Subsequences

Medium

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⁹ + 7.

Example 1:

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:

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:

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⁵
0 <= nums[i] <= 10⁹
1 <= k <= min(70, nums.length)

Solution¶

import java.util.Arrays;

class Solution {
    private long[] factorials = new long[(int)(1e5 + 10)];
    private long[] invFactorials = new long[(int)(1e5 + 10)];
    private int mod = (int)(1e9 + 7);
    public int minMaxSums(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);

        preCompFacts();

        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                ans = add(ans, mul((long)(nums[i] * 1L), nCk(n - i - 1, j - 1)));
                ans = add(ans, mul((long)(nums[i] * 1L), nCk(i, j - 1)));
            }
        }
        return (int)(ans);
    }

    private void preCompFacts() {
        factorials[0] = invFactorials[0] = 1;
        for (int i = 1; i < factorials.length; i++)
            factorials[i] = mul(factorials[i - 1], i);
        invFactorials[factorials.length - 1] = exp(factorials[factorials.length - 1], mod - 2);
        for (int i = invFactorials.length - 2; i >= 0; i--)
            invFactorials[i] = mul(invFactorials[i + 1], i + 1);
    }

    private long nCk(int n, int k) {
        if (n - k < 0)
            return 0;
        return mul(factorials[n], mul(invFactorials[k], invFactorials[n - k]));
    }

    private long exp(long base, long exp) {
        if (exp == 0)
            return 1;
        long half = exp(base, exp / 2);
        if (exp % 2 == 0)
            return mul(half, half);
        return mul(half, mul(half, base));
    }

    private long add(long a, long b) {
        a += b;
        if (a >= mod)
            a -= mod;
        return a;
    }

    private long mul(long a, long b) {
        return (long)((long)((a % mod) * 1L * (b % mod)) % mod);
    }


}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here