Given two integers N and K. There are N balls placed in a row. K of them are green and N – K of them are black. The task is to find the number of ways to arrange N balls such that one will need exactly i ( 1 ? i ? K ) moves to collect all the green balls. In one move, we can collect any group of consecutive green balls. Note that the answer can be very large. So, output answer modulo 109 + 7.
Examples:
Input: N = 5, K = 3
Output: 3 6 1
There are three ways to arrange the balls so that
one will need exactly one move:
(G, G, G, B, B), (B, G, G, G, B), and (B, B, G, G, G).
There are six ways to arrange the balls so that
one will need exactly two moves:
(G, G, B, G, B), (G, G, B, B, G), (B, G, G, B, G), (B, G, B, G, G),
(G, B, G, G, B), and (G, B, B, G, G).
There is only one way to arrange the balls so that
one will need exactly three moves: (G, B, G, B, G).Input: N = 100, K = 5
Output: 96 18240 857280 13287840 61124064
Approach: Only i moves have to be performed to collect K green balls, which means that K green balls are separated into i places by black balls. Therefore, let’s consider the combination as follows.
- First, arrange the N – K black balls in a row.
- In between these black balls, select i places from the left end to the right end and consider placing K green balls there. There are N – K + 1C i ways to choose these.
- For each choice, consider how many green balls will be assigned to each gap. Since it is necessary to assign one or more to each, there are K – 1C i – 1 ways to determine this.
Therefore, for each i, the answer is N – K + 1C i * K – 1C i – 1 . Finding n C r is discussed here.
Below is the implementation of the above approach:
C++
// 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 ways to arrange K green// balls among N balls such that we need// exactly i moves to collect all K green ballsvoid arrange_balls(int n, int k){ factorialfun(); modinversefun(); for (int i = 1; i <= k; i++) cout << (1LL * binomial(n - k + 1, i) * binomial(k - 1, i - 1)) % mod << " ";}// Driver codeint main(){ int n = 5, k = 3; // Function call arrange_balls(n, k); return 0;} |
Python3
# Python3 implementation of the approach N = 100005mod = (int)(1e9 + 7) # To store the factorial and the # factorial mod inverse of a number factorial = [0] * N;modinverse = [0] * N; # Function to find (a ^ m1) % mod def power(a, m1) : if (m1 == 0) : return 1; elif (m1 == 1) : return a; elif (m1 == 2) : return (a * a) % mod; elif (m1 & 1) : 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 def 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 numbers def modinversefun() : modinverse[N - 1] = power(factorial[N - 1], mod - 2) % mod; for i in range(N - 2 , -1, -1) : modinverse[i] = (modinverse[i + 1] * (i + 1)) % mod; # Function to return nCr def 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 ways to arrange K green # balls among N balls such that we need # exactly i moves to collect all K green balls def arrange_balls(n, k) : factorialfun(); modinversefun(); for i in range(1, k + 1) : print((binomial(n - k + 1, i) * binomial(k - 1, i - 1)) % mod, end = " "); # Driver code if __name__ == "__main__" : n = 5; k = 3; # Function call arrange_balls(n, k); # This code is contributed by AnkitRai01 |
Java
// Java implementation of the approachimport java.util.*;class GFG{static final int N = 100005;static final int mod = (int)(1e9 + 7);// To store the factorial and the// factorial mod inverse of a numberstatic long []factorial = new long[N];static long []modinverse = new long[N];// Function to find (a ^ m1) % modstatic long power(long a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1L * a * a) % mod; else if (m1 %2== 1) return (1L * 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] = (1L * factorial[i - 1] * i) % mod;}// Function to find the factorial// mod inverse of all the numbersstatic void modinversefun(){ modinverse[N - 1] = (int) (power(factorial[N - 1], mod - 2) % mod); for (int i = N - 2; i >= 0; i--) modinverse[i] = (1 * modinverse[i + 1] * (i + 1)) % mod;}// Function to return nCrstatic long binomial(int n, int r){ if (r > n) return 0; long a = (1L * factorial[n] * modinverse[n - r]) % mod; a = (1 * a * modinverse[r]) % mod; return a;}// Function to find ways to arrange K green// balls among N balls such that we need// exactly i moves to collect all K green ballsstatic void arrange_balls(int n, int k){ factorialfun(); modinversefun(); for (int i = 1; i <= k; i++) System.out.print((1L * binomial(n - k + 1, i) * binomial(k - 1, i - 1)) % mod + " ");}// Driver codepublic static void main(String[] args){ int n = 5, k = 3; // Function call arrange_balls(n, k);}}// This code contributed by Princi Singh |
C#
// C# implementation of the approachusing System;class GFG{ static readonly int N = 100005;static readonly int mod = (int)(1e9 + 7);// To store the factorial and the// factorial mod inverse of a numberstatic long []factorial = new long[N];static long []modinverse = new long[N];// Function to find (a ^ m1) % modstatic long power(long a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1L * a * a) % mod; else if (m1 % 2 == 1) return (1L * 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] = (1L * factorial[i - 1] * i) % mod;}// Function to find the factorial// mod inverse of all the numbersstatic void modinversefun(){ modinverse[N - 1] = (int)(power(factorial[N - 1], mod - 2) % mod); for(int i = N - 2; i >= 0; i--) modinverse[i] = (1 * modinverse[i + 1] * (i + 1)) % mod;}// Function to return nCrstatic long binomial(int n, int r){ if (r > n) return 0; long a = (1L * factorial[n] * modinverse[n - r]) % mod; a = (1 * a * modinverse[r]) % mod; return a;}// Function to find ways to arrange K green// balls among N balls such that we need// exactly i moves to collect all K green ballsstatic void arrange_balls(int n, int k){ factorialfun(); modinversefun(); for(int i = 1; i <= k; i++) Console.Write((1L * binomial(n - k + 1, i) * binomial(k - 1, i - 1)) % mod + " ");}// Driver codepublic static void Main(String[] args){ int n = 5, k = 3; // Function call arrange_balls(n, k);}}// This code is contributed by 29AjayKumar |
Javascript
// Function to find (a ^ m1) % modfunction power(a, m1) { if (m1 == 0) return BigInt(1); else if (m1 == 1) return BigInt(a); else if (m1 == 2) return BigInt(a * a) % BigInt(mod); else if (m1 % BigInt(2) === BigInt(1)) return BigInt(a * power(power(a, m1 / BigInt(2)), BigInt(2))) % BigInt(mod); else return power(power(a, m1 / BigInt(2)), BigInt(2)) % BigInt(mod);}function factorialfun() { factorial[0] = 1n; for (let i = 1; i < N; i++) factorial[i] = factorial[i - 1] * BigInt(i) % BigInt(mod);}function modinversefun() { modinverse[N - 1] = power(factorial[N - 1], BigInt(mod - 2)) % BigInt(mod); for (let i = N - 2; i >= 0; i--) modinverse[i] = modinverse[i + 1] * BigInt(i + 1) % BigInt(mod);}function binomial(n, r) { if (r > n) return 0; let a = factorial[n] * modinverse[n - r] % BigInt(mod); a = a * modinverse[r] % BigInt(mod); return a;}function arrange_balls(n, k) { factorialfun(); modinversefun(); for (let i = 1; i <= k; i++) console.log(binomial(n - k + 1, i) * binomial(k - 1, i - 1) % BigInt(mod) + " ");}const N = 100005;const mod = 1e9 + 7;let factorial = new Array(N);let modinverse = new Array(N);const n = 5, k = 3;arrange_balls(n, k); |
Output:
3 6 1
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!
