Given an array arr[] of size N and an integer K. The task is to find the sum of f(S) over all the possible sets. For a finite set X, f(X) is max(X) – min(X). Set X contains any K numbers from the given array. Output can be very large, so, output answer modulo 109+7. Examples:
Input: arr[] = {1, 1, 3, 4}, K = 2 Output: 11 Sets are {1, 1}, {1, 3}, {1, 4}, {1, 3}, {1, 4}, {3, 4} and f(X) are 0, 2, 3, 2, 3, 1. Input: arr[] = {10, -10, 10, -10, 10, -10}, K = 3 Output: 360 18 sets with f(X) equals to 20 and 2 sets with f(x) equals to 0
Approach: On assuming that arr is sorted beforehand, the idea is to perform precomputation to calculate binomial coefficients fast by precalculating the factorials till N and their inverses. The sum is calculated separately for min and max. In other words, (? max(S)) – (? min(S)) instead of ? f(S). For simplicity, assume that arri is distinct from each other. The possible value of max(S) is any element of arr. Therefore, by counting the number of S such that max(S) = arri for each i, you can find ? max(S). The necessary and sufficient condition of max(S) = arri is S contains arri, and also contains K-1 elements less than arri, so such number can be directly calculated by using binomial coefficients. You can calculate ? minS similarly. If Ai contains duplicates, you can prove that the explanation above also holds if you assume arbitrary order between arr is with the same value (for example, consider a lexicographical order of(arri, i and count the number of elements satisfying max(S) = (Ai, i). Therefore, you can also process in the same way in this case. Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100005#define mod (int)(1e9 + 7)// To store the factorial and the// factorial mod inverse of a numberint factorial[N], modinverse[N];// Function to find (a ^ m1) % modint power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1LL * a * a) % mod; else if (m1 & 1) return (1LL * a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to find factorial// of all the numbersvoid factorialfun(){ factorial[0] = 1; for (int i = 1; i < N; i++) factorial[i] = (1LL * factorial[i - 1] * i) % mod;}// Function to find the factorial// mod inverse of all the numbersvoid modinversefun(){ modinverse[N - 1] = power(factorial[N - 1], mod - 2) % mod; for (int i = N - 2; i >= 0; i--) modinverse[i] = (1LL * modinverse[i + 1] * (i + 1)) % mod;}// Function to return nCrint binomial(int n, int r){ if (r > n) return 0; int a = (1LL * factorial[n] * modinverse[n - r]) % mod; a = (1LL * a * modinverse[r]) % mod; return a;}// Function to find sum of f(s) for all// the chosen sets from the given arrayint max_min(int a[], int n, int k){ // Sort the given array sort(a, a + n); // Calculate the factorial and // modinverse of all elements factorialfun(); modinversefun(); long long ans = 0; k--; // For all the possible sets // Calculate max(S) and min(S) for (int i = 0; i < n; i++) { int x = n - i - 1; if (x >= k) ans -= binomial(x, k) * a[i] % mod; int y = i; if (y >= k) ans += binomial(y, k) * a[i] % mod; ans = (ans + mod) % mod; } return (int)(ans);}// Driver codeint main(){ int a[] = { 1, 1, 3, 4 }, k = 2; int n = sizeof(a) / sizeof(int); cout << max_min(a, n, k); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int N = 100005;static int mod = 1000000007;static int temp = 391657242;// To store the factorial and the// factorial mod inverse of a numberstatic int []factorial = new int[N];static int []modinverse = new int[N];// Function to find (a ^ m1) % modstatic int power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (a * a) % mod; else if ((m1 & 1)!=0) return (a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to find factorial// of all the numbersstatic void factorialfun(){ factorial[0] = 1; for (int i = 1; i < N; i++) factorial[i] = (factorial[i - 1] * i)% mod;}// Function to find the factorial// mod inverse of all the numbersstatic void modinversefun(){ modinverse[N - 1] = power(factorial[N - 1], mod - 2) % mod; for (int i = N - 2; i >= 0; i--) modinverse[i] = (modinverse[i + 1]*(i + 1))%mod;}// Function to return nCrstatic int binomial(int n, int r){ if (r > n) return 0; int a = (factorial[n] * modinverse[n - r]) % mod; a = (a * modinverse[r]) % mod; return a;}// Function to find sum of f(s) for all// the chosen sets from the given arraystatic int max_min(int a[], int n, int k){ // Sort the given array Arrays.sort(a); // Calculate the factorial and // modinverse of all elements factorialfun(); modinversefun(); int ans = 0; k--; // For all the possible sets // Calculate max(S) and min(S) for (int i = 0; i < n; i++) { int x = n - i - 1; if (x >= k) ans -= binomial(x, k) * a[i] % mod; int y = i; if (y >= k) ans += binomial(y, k) * a[i] % mod; ans = (ans + mod) % mod; } return ans%temp;}// Driver codepublic static void main(String args[]){ int []a = { 1, 1, 3, 4 }; int k = 2; int n = a.length; System.out.println(max_min(a, n, k));}}// This code is contributed by Surendra_Gangwar |
Python3
# Python3 implementation of the approachN = 100005mod = (10 ** 9 + 7)# To store the factorial and the# factorial mod inverse of a numberfactorial = [0]*Nmodinverse = [0]*N# Function to find factorial# of all the numbersdef factorialfun(): factorial[0] = 1 for i in range(1, N): factorial[i] = (factorial[i - 1] * i)%mod# Function to find the factorial# mod inverse of all the numbersdef modinversefun(): modinverse[N - 1] = pow(factorial[N - 1], mod - 2, mod) % mod for i in range(N - 2, -1, -1): modinverse[i] = (modinverse[i + 1]* (i + 1))% mod# Function to return nCrdef binomial(n, r): if (r > n): return 0 a = (factorial[n]* modinverse[n - r])% mod a = (a * modinverse[r]) % mod return a# Function to find sum of f(s) for all# the chosen sets from the given arraydef max_min(a, n, k): # Sort the given array a = sorted(a) # Calculate the factorial and # modinverse of all elements factorialfun() modinversefun() ans = 0 k -= 1 # For all the possible sets # Calculate max(S) and min(S) for i in range(n): x = n - i - 1 if (x >= k): ans -= (binomial(x, k) * a[i]) % mod y = i if (y >= k): ans += (binomial(y, k) * a[i]) % mod ans = (ans + mod) % mod return ans# Driver codea = [1, 1, 3, 4]k = 2n = len(a)print(max_min(a, n, k))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; class GFG{ static int N = 100005; static int mod = 1000000007; static int temp = 391657242; // To store the factorial and the // factorial mod inverse of a number static int []factorial = new int[N]; static int []modinverse = new int[N]; // Function to find (a ^ m1) % mod static int power(int a, int m1) { if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (a * a) % mod; else if ((m1 & 1)!=0) return (a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod; } // Function to find factorial // of all the numbers static void factorialfun() { factorial[0] = 1; for (int i = 1; i < N; i++) factorial[i] = (factorial[i - 1] * i)% mod; } // Function to find the factorial // mod inverse of all the numbers static void modinversefun() { modinverse[N - 1] = power(factorial[N - 1], mod - 2) % mod; for (int i = N - 2; i >= 0; i--) modinverse[i] = (modinverse[i + 1]*(i + 1)) % mod; } // Function to return nCr static int binomial(int n, int r) { if (r > n) return 0; int a = (factorial[n] * modinverse[n - r]) % mod; a = (a * modinverse[r]) % mod; return a; } // Function to find sum of f(s) for all // the chosen sets from the given array static int max_min(int []a, int n, int k) { // Sort the given array Array.Sort(a); // Calculate the factorial and // modinverse of all elements factorialfun(); modinversefun(); int ans = 0; k--; // For all the possible sets // Calculate max(S) and min(S) for (int i = 0; i < n; i++) { int x = n - i - 1; if (x >= k) ans -= binomial(x, k) * a[i] % mod; int y = i; if (y >= k) ans += binomial(y, k) * a[i] % mod; ans = (ans + mod) % mod; } return ans % temp; } // Driver code public static void Main(string []args) { int []a = { 1, 1, 3, 4 }; int k = 2; int n = a.Length; Console.WriteLine(max_min(a, n, k)); } } // This code is contributed by AnkitRai01 |
Javascript
// JS implementation of the approachlet N = 100005let mod = BigInt(1e9 + 7)// To store the factorial and the// factorial mod inverse of a numberlet factorial = new Array(N)let modinverse = new Array(N);// Function to find (a ^ m1) % modfunction power(a, m1){ if (m1 == 0n) return 1n; else if (m1 == 1n) return a; else if (m1 == 2n) return (a * a) % mod; else if (m1 & 1n) return (a * power(power(a, m1 / 2n), 2n)) % mod; else return power(power(a, m1 / 2n), 2n) % mod;}// Function to find factorial// of all the numbersfunction factorialfun(){ factorial[0] = 1n; for (let i = 1n; i < N; i++) factorial[i] = (factorial[i - 1n] * i) % mod;}// Function to find the factorial// mod inverse of all the numbersfunction modinversefun(){ modinverse[N - 1] = power(factorial[N - 1], mod - 2n) % mod; N = BigInt(N) for (var i = N - 2n; i >= 0n; i--) modinverse[i] = (modinverse[i + 1n] * (i + 1n)) % mod;}// Function to return nCrfunction binomial(n, r){ if (r > n) return 0n; let a = (factorial[n] * modinverse[n - r]) % mod; a = (a * modinverse[r]) % mod; return a;}// Function to find sum of f(s) for all// the chosen sets from the given arrayfunction max_min(a, n, k){ n = BigInt(n) // Sort the given array a.sort(); // Calculate the factorial and // modinverse of all elements factorialfun(); modinversefun(); let ans = 0n; k--; // For all the possible sets // Calculate max(S) and min(S) for (var i = 0n; i < n; i++) { var x = n - i - 1n; if (x >= k) ans -= binomial(x, k) * a[i] % mod; var y = i; if (y >= k) ans += binomial(y, k) * a[i] % mod; ans = (ans + mod) % mod; } return (ans);}// Driver codelet a= [ 1n, 1n, 3n, 4n ]let k = 2n;let n = a.lengthconsole.log(max_min(a, n, k))// This code is contributed by phasing17 |
Output:
11
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
