We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum and Minimum Sums of at Most Size K Subsequences

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each element in the array can contribute to the minimum and maximum of multiple subsequences.
  • To compute the total contribution of each element to the final sum, we can utilize combinatorial counting.
  • The combinations of elements can be calculated using binomial coefficients to determine how many times each element will be the minimum or maximum in valid subsequences.
  • The constraints allow for a maximum of 70 elements to be considered in the subsequences, making combinatorial calculations feasible.

Space and Time Complexity

Time Complexity: O(n + k^2)
Space Complexity: O(k)

Solution

To solve this problem, we:

  1. Sort the nums array to easily access the smallest and largest elements.
  2. Use combinatorial mathematics to calculate how many times each element contributes as a minimum and maximum in subsequences of size ranging from 1 to k.
  3. For each element, calculate its contribution based on how many valid subsequences can be formed with it as the minimum or maximum.
  4. Sum these contributions and return the result modulo 10^9 + 7.

Code Solutions

def max_min_sums(nums, k):
    MOD = 10**9 + 7
    n = len(nums)
    nums.sort()
    
    # Precompute factorials and inverse factorials for binomial coefficients
    fact = [1] * (k + 1)
    for i in range(2, k + 1):
        fact[i] = fact[i - 1] * i % MOD

    def binomial(n, r):
        if r > n or r < 0:
            return 0
        return fact[n] * pow(fact[r], MOD - 2, MOD) * pow(fact[n - r], MOD - 2, MOD) % MOD
    
    total_sum = 0
    
    # Calculate contribution for minimums
    for i in range(n):
        # Count how many subsequences can include nums[i] as minimum
        for j in range(1, k + 1):
            total_sum += nums[i] * binomial(n - i - 1, j - 1)
            total_sum %= MOD
    
    # Calculate contribution for maximums
    for i in range(n):
        # Count how many subsequences can include nums[i] as maximum
        for j in range(1, k + 1):
            total_sum += nums[i] * binomial(i, j - 1)
            total_sum %= MOD

    return total_sum

# Example usage
print(max_min_sums([1, 2, 3], 2))  # Output: 24
← Back to All Questions