Precalculate number of ways to form subsets with n as minimum/maximum for valid n.

Use of (n+1)Cr = nCr * (n+1)/(n+1-r) for efficient calculation of nCr for incrementing n and fixed r

O(n) solution

def solve(balls, k): MOD = 10**9+7 result = 0 n = len(balls) balls.sort()

memo = {}
memo[k-1] = math.comb(k-1, k-1)
for i in range(k, n+1):
    memo[i] = memo[i-1] * i // (i-(k-1))
for i in range(n-k+1):
    result -= balls[i] * memo[n-1-i]
for i in range(k-1, n):
    result += balls[i] * memo[i]
return result % MOD

Hi everyone, I get TLE for the last 4 test cases... please advise me on how to optimize the code. Thank you!

>

mod = 10**9 + 7 def solve(balls, k): if k == 1: return 0

balls.sort()
ans = 0
n = len(balls)

for i, ball in enumerate(balls):
    if i >= k-1:
        ans += ball * (comb(i, k-1))

    if i < n-k+1:
        ans -= ball * comb(n-i-1, k-1)

return ans % mod

I am running a scholarships website for international students on wordpress. Can I use this,"Choose and Calculate" functions in my website for smooth and easy data input?

have coded the following (naive) O(n^2) solution code below. (Sorry HackerRank people for posting code, I'll not do it again :-) ) It passes only a few test cases and times out as I expected on others. Can anyone see a problem with the logic?

Could someone explain what the loops mean? This is taken from Editorial

    for(int i=k; i<=n; i++) ans += a[i] * C(i-1, k-1) % MOD;
for(int i=1; i<=n-k+1; i++) ans -= a[i] * C(n-i, k-1) % MOD;