T(n, k, M) = O(nlog(n) + log(M) + nk) - Fermat's Little Theorem / Combinations
Complexity

Worst-case time complexity:
T(n,k,M)=Θ(nlogn+logM+nk)



n= the size of nums




k= the maximum subsequence size




M= the given modulus (a constan
# Complexity
- Worst-case time complexity:
$T(n, k, M) = \Theta(n \log n + \log M + nk)$
- - $n =$ the size of `nums`
- - $k =$ the maximum subsequence size
- - $M =$ the given modulus (a constant `10 ** 9 + 7` in this context, but the algorithm's runtime depends on it due to the `pow()` implementation.)

- Worst-case auxiliary space complexity:
$S(n, k, M) = \Theta(n)$ (I think)

# Intuition
My initial approach was to handwrite example lists around size 5 until I could figure out a pattern. It became apparent that, if the input is sorted, you can use combinatorics to accurately predict the amount of each element in the final sum (ignoring modulo arithmetic).

Example: `[a, b, c, d, e]`, `k = 5`

I won't write out the entire lists of subsequences here, but if you'd like to check my work in an itemized way, please feel free!

For the 5 subsequences of size 1, the set of minimums contains 1 a, 1 b, 1 c, 1 d, and 1 e. The set of maximums followed a similar pattern. For brevity's sake, I'll skip ahead to notating these coefficients as combinations even though that pattern only became apparent later on in my actual work:

$minsum_{1} = \binom{4}{0}a + \binom{3}{0}b + \binom{2}{0}c + \binom{1}{0}d + \binom{0}{0}e$
$maxsum_{1} = \binom{4}{0}e + \binom{3}{0}d + \binom{2}{0}c + \binom{1}{0}b + \binom{0}{0}a$
$subsum_{1} = \binom{4}{0}(a+e) + \binom{3}{0}(b+d) + \binom{2}{0}(c+c) + \binom{1}{0}(d+b) + \binom{0}{0}(e+a)$

For the 10 subsequences of size 2, we have a different pattern in the minimums: 4 a's, 3 b's, 2 c's, 1 d, and 0 e's. The maximums had the same amounts, but naturally applied to the largest elements from 'e' downward instead of the smallest.

$minsum_{2} = \binom{4}{1}a + \binom{3}{1}b + \binom{2}{1}c + \binom{1}{1}d$
$maxsum_{2} = \binom{4}{1}e + \binom{3}{1}d + \binom{2}{1}c + \binom{1}{1}b$
$subsum_{2} = \binom{4}{1}(a+e) + \binom{3}{1}(b+d) + \binom{2}{1}(c+c) + \binom{1}{1}(d+b)$

You may notice that we lost the "final" term from the previous set of sums. I believe this can also be thought of as the term where the coefficient is $\binom{0}{1} = 0$, but I think it's cleaner to just omit the term for this writeup.

For the 10 subsequences of size 3, we have:

$minsum_{3} = \binom{4}{2}a + \binom{3}{2}b + \binom{2}{2}c$
$maxsum_{3} = \binom{4}{2}e + \binom{3}{2}d + \binom{2}{2}c$
$subsum_{3} = \binom{4}{2}(a+e) + \binom{3}{2}(b+d) + \binom{2}{2}(c+c)$

For the 5 subsequences of size 4, we have:

$minsum_{4} = \binom{4}{3}a + \binom{3}{3}b$
$maxsum_{4} = \binom{4}{3}e + \binom{3}{3}d$
$subsum_{4} = \binom{4}{3}(a+e) + \binom{3}{3}(b+d)$

And finally, for the 1 subsequence of size 5, we have:

$minsum_{5} = \binom{4}{4}a$
$maxsum_{5} = \binom{4}{4}e$
$subsum_{5} = \binom{4}{4}(a+e)$

It eventually becomes apparent that for each set of subsequences of a certain size, our solution will contain the same amount of a's and e's, the same amount of b's and d's, and so on. In other words, for subsequences of size `subsize` and elements `nums[i]` and `nums[n - 1 - i]`, there are `C(n - 1 - i, subsize - 1)` amount of both in the final solution (pre-modulo).

With unlimited computation, our code could look something like this:

```
result = 0
for subsize = 1 to k:
    for i = 0 to n-1:
        result += C(n - 1 - i, subsize - 1) * (nums[i] + nums[n - 1 - i])
return result % M
```

Unfortunately, this approach would not pass the time limit and I could not pass the final few test cases before the contest ended no matter what I tried 😭. During my subsequent research, I discovered a method that involves using Fermat's Little Theorem to calculate combinations efficiently with modular multiplication, which seems to be the only way to get it under the time limit.

# Approach
Without going into extreme detail, the fact that our final solution requires modular arithmetic means that we can take advantage of properties of modular arithmetic to optimize our computational complexity.

For example, instead of calculating $C(n,r) \bmod M= \frac{n!}{r!(n-r)!} \bmod M$ directly, which would be inefficient due to the factorials involved, we can precompute some intermediate values — factorials mod M up to `n`, and the modular multiplicative inverse of each of those factorials (mod M).

In this problem, the modular multiplicative inverse (MMI) of $i!$ is $(i!)^{M-2} \bmod M$. There is another optimization in the code below that utilizes the following facts:

$(i+1)! = i! \cdot (i+1)$ — definition of a factorial

$(i+1)!^{-1} \equiv i!^{-1} \cdot (i+1)^{-1} \pmod{M}$ — property of MMI $\pmod{M}$

$(i+1)!^{-1} \cdot (i+1) \equiv i!^{-1} \pmod{M}$ — multiply both sides by $(i+1) \pmod{M}$

Now, we can efficiently calculate `C(n, r) % M` as, roughly speaking, `(modfact[n] * (inv_modfact[r] * inv_modfact[n-r]) % M) % M`.


<!-- Describe your approach to solving the problem. -->


# Code
```python3 []
class Solution:
    # The given modulus; a prime number compatible with Fermat's Little Theorem.
    M: int = (10 ** 9) + 7

    def minMaxSums(
        self, 
        nums: List[int], 
        k: int
    ) -> int:
        """Overall time complexity: O(nlog(n) + log(M) + nk)"""

        # O(1): Name relevant variables.
        n: int = len(nums)

        # O(n log n): Min/max nums must be in expected order.
        nums.sort()

        # O(n): Precompute factorials (mod M).
        mod_fact: list[int] = [1 for _ in range(n + 1)]
        for i in range(2, n + 1): # Given: 0! = 1! = 1 (mod anything).
            mod_fact[i] = (mod_fact[i - 1] * i) % self.M
            
        # O(n): Precompute modular multiplicative inverse of each factorial.
        mod_inv_fact: list[int] = [1 for _ in range(n + 1)]

        # O(log M): Initialize using Fermat's Little Theorem.
        # Note that pow() function operates in log(exponent).
        mod_inv_fact[n] = pow(mod_fact[n], self.M - 2, self.M)

        # O(n): Fast backward computation based on below recurrence:
        # inv(i!) = inv((i+1)!) * (i + 1) mod M
        for i in range(n - 1, 0, -1):
            mod_inv_fact[i] = (mod_inv_fact[i + 1] * (i + 1)) % self.M

        # O(nk): Compute the result.
        result: int = 0
        for sub_size in range(1, k + 1):
            for i in range(n - sub_size + 1):
                # Count subseq with min/max located 'i' away from ends of nums.
                remaining_n: int = n - 1 - i
                remaining_sub_size: int = sub_size - 1
                num_of_subseq: int = self.fast_combination(
                    mod_fact, 
                    mod_inv_fact, 
                    remaining_n, 
                    remaining_sub_size
                )

                # Add contribution from min and max of the current subsequence.
                sub_min: int = nums[i]
                sub_max: int = nums[n - 1 - i]
                result += (num_of_subseq * (sub_min + sub_max)) % self.M
                result %= self.M

        return result
    
    def fast_combination(
        self, 
        mod_fact: list[int], 
        mod_inv_fact: list[int], 
        n: int, 
        r: int
    ) -> int:
        """Compute C(n, r) % M efficiently given a list of factorials (mod 
        self.M) and the modular inverse (MMI) of each factorial with
        respect to modulo self.M.

        Args:
            mod_fact: A list of factorials modulo self.M.

            mod_inv_fact: A list of the modular multiplicative inverse for
                each factorial with respect to modulo self.M.

            n: The 'n' in "n choose r".

            r: The 'r' in "n choose r".

        Returns:
            C(n, r) % self.M.
        """

        numerator: int = mod_fact[n]
        inv_denominator: int = (mod_inv_fact[r] * mod_inv_fact[n - r]) % self.M
        result: int = (numerator * inv_denominator) % self.M
        return result


```
['Python3']