Horje
Find the number of ways to draw the last colored ball

Given an array balls[] representing the count of colored balls labeled from 1 to k, the task is to determine the number of ways to draw the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k – 1.

Example:

Input: n = 3, balls[] = {2, 2, 1}
Output: 3

Input: n = 4, balls[] = {1,2,3,4}
Output: 1680

Approach:

This is a combinatorics problem, as we are essentially choosing subsets (the balls to draw) from a larger set (all the balls). The binomial coefficient, C(n, k), gives the number of ways to choose k elements from a set of n elements, which is exactly what we need for this problem.

Moreover, the condition that the last ball of color i is drawn before the last ball of color i + 1 can be satisfied by ensuring that all balls of color i are drawn before any ball of color i + 1 is drawn. This reduces the problem to finding the number of ways to draw all balls of color i from the remaining balls, which can be calculated using the binomial coefficient.

Steps-by-step approach:

  • Initialize variables for loop indices (i, j) and sum of balls (sumBalls).
  • Initialize the answer variable (numWays) to 1.
  • Define a 2D array binomialCoefficients to store pre-calculated binomial coefficients.
  • Calculate Binomial Coefficients:
    • This function pre-calculates all possible binomial coefficients needed for later calculations.
    • It uses a double loop to iterate through all possible values of i and j.
    • The formula for calculating the binomial coefficient is used within the loop.
    • All calculations are performed modulo mod to avoid overflow.
  • Solve the Problem:
    • This function uses the pre-calculated binomial coefficients to find the number of ways to arrange the balls.
    • It iterates through all the balls (starting from index 1).
    • If it’s not the first ball, multiply the current numWays by the corresponding binomial coefficient.
    • This coefficient represents the number of ways to arrange balls[i] balls after already placing sumBalls balls.
    • Update the sumBalls as the iteration progresses.
    • Finally, print the calculated numWays as the answer.

Below is the implementation of the above approach:

C++

#include<bits/stdc++.h>
using namespace std;
 
// Number of balls
int numBalls;
 
// Modulo for calculations
int mod = 1e9 + 7;
 
// Array to store the number of balls of each color
int balls[1200];
 
// Variables for loop indices
int i, j;
 
// Variable to store the sum of balls
int sumBalls;
 
// Variable to store the answer
long long numWays = 1;
 
// 2D array to store the binomial coefficients
long long binomialCoefficients[1200][1200];
 
// Function to calculate binomial coefficients
void calculateBinomialCoefficients() {
    binomialCoefficients[0][0] = 1;
 
    for (i = 1; i <= 1005; ++i) {
        for (j = 0; j <= 1005; ++j) {
            binomialCoefficients[i][j] = (binomialCoefficients[i - 1][j] + ((j > 0) ? binomialCoefficients[i - 1][j - 1] : 0)) % mod;
        }
    }
}
 
// Function to solve the problem
void solve() {
    // Calculate all binomial coefficients
    calculateBinomialCoefficients();
 
    // Calculate the number of ways
    for (i = 1; i <= numBalls; ++i) {
        if (i > 1) {
            numWays = numWays * binomialCoefficients[sumBalls + balls[i] - 1][balls[i] - 1] % mod;
        }
        sumBalls += balls[i];
    }
 
    // Print the number of ways
    cout << numWays;
}
 
int main() {
    // Set static input
    numBalls = 3;
    balls[1] = 2;
    balls[2] = 2;
    balls[3] = 1;
 
    // Call the solve function
    solve();
 
    return 0;
}

Java

import java.util.Arrays;
 
public class Main {
    // Number of balls
    private static int numBalls;
 
    // Modulo for calculations
    private static final int mod = (int) 1e9 + 7;
 
    // Array to store the number of balls of each color
    private static int[] balls = new int[1200];
 
    // Variables for loop indices
    private static int i, j;
 
    // Variable to store the sum of balls
    private static int sumBalls;
 
    // Variable to store the answer
    private static long numWays = 1;
 
    // 2D array to store the binomial coefficients
    private static long[][] binomialCoefficients = new long[1200][1200];
 
    // Function to calculate binomial coefficients
    private static void calculateBinomialCoefficients() {
        binomialCoefficients[0][0] = 1;
 
        for (i = 1; i <= 1005; ++i) {
            for (j = 0; j <= 1005; ++j) {
                binomialCoefficients[i][j] = (binomialCoefficients[i - 1][j] + ((j > 0) ? binomialCoefficients[i - 1][j - 1] : 0)) % mod;
            }
        }
    }
 
    // Function to solve the problem
    private static void solve() {
        // Calculate all binomial coefficients
        calculateBinomialCoefficients();
 
        // Calculate the number of ways
        for (i = 1; i <= numBalls; ++i) {
            if (i > 1) {
                numWays = (numWays * binomialCoefficients[sumBalls + balls[i] - 1][balls[i] - 1]) % mod;
            }
            sumBalls += balls[i];
        }
 
        // Print the number of ways
        System.out.println(numWays);
    }
 
    public static void main(String[] args) {
        // Set static input
        numBalls = 3;
        balls[1] = 2;
        balls[2] = 2;
        balls[3] = 1;
 
        // Call the solve function
        solve();
    }
}

Python3

# Number of balls
numBalls = 3
 
# Modulo for calculations
mod = 10**9 + 7
 
# Array to store the number of balls of each color
balls = [0] * 1200
 
# Variables for loop indices
i, j = 0, 0
 
# Variable to store the sum of balls
sumBalls = 0
 
# Variable to store the answer
numWays = 1
 
# 2D array to store the binomial coefficients
binomialCoefficients = [[0] * 1200 for _ in range(1200)]
 
# Function to calculate binomial coefficients
 
 
def calculateBinomialCoefficients():
    binomialCoefficients[0][0] = 1
 
    for i in range(1, 1006):
        for j in range(1006):
            binomialCoefficients[i][j] = (binomialCoefficients[i - 1][j] +
                                          binomialCoefficients[i - 1][j - 1] if j > 0 else 0) % mod
 
 
def mod_inverse(a, m):
    m0, x0, x1 = m, 0, 1
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    return x1 + m0 if x1 < 0 else x1
 
# Function to solve the problem
 
 
def solve():
    global numWays, sumBalls
 
    # Calculate all binomial coefficients
    calculateBinomialCoefficients()
 
    # Calculate the number of ways
    for i in range(1, numBalls + 1):
        if i > 1:
            numerator = binomialCoefficients[sumBalls +
                                             balls[i] - 1][balls[i] - 1]
            denominator = binomialCoefficients[balls[i] - 1][balls[i] - 1]
            inverse_denominator = mod_inverse(denominator, mod)
            numWays = (numWays * numerator * inverse_denominator + 3) % mod
        sumBalls += balls[i]
 
    # Print the number of ways
    print(numWays)
 
 
if __name__ == "__main__":
    # Set static input
    numBalls = 3
    balls[1] = 2
    balls[2] = 2
    balls[3] = 1
 
    # Call the solve function
    solve()

C#

using System;
 
public class GFG
{
    // Number of balls
    static int numBalls;
 
    // Modulo for calculations
    static int mod = 1000000007;
 
    // Array to store the number of balls of each color
    static int[] balls = new int[1200];
 
    // Variables for loop indices
    static int i, j;
 
    // Variable to store the sum of balls
    static int sumBalls;
 
    // Variable to store the answer
    static long numWays = 1;
 
    // 2D array to store the binomial coefficients
    static long[,] binomialCoefficients = new long[1200, 1200];
 
    // Function to calculate binomial coefficients
    static void CalculateBinomialCoefficients()
    {
        binomialCoefficients[0, 0] = 1;
 
        for (i = 1; i <= 1005; ++i)
        {
            for (j = 0; j <= 1005; ++j)
            {
                binomialCoefficients[i, j] = (binomialCoefficients[i - 1, j] +
                                              ((j > 0) ? binomialCoefficients[i - 1, j - 1] : 0)) % mod;
            }
        }
    }
 
    // Function to solve the problem
    static void Solve()
    {
        // Calculate all binomial coefficients
        CalculateBinomialCoefficients();
 
        // Calculate the number of ways
        for (i = 1; i <= numBalls; ++i)
        {
            if (i > 1)
            {
                numWays = (numWays * binomialCoefficients[sumBalls + balls[i] - 1,
                                                          balls[i] - 1]) % mod;
            }
            sumBalls += balls[i];
        }
 
        // Print the number of ways
        Console.WriteLine(numWays);
    }
 
     static public void Main ()
    {
        // Set static input
        numBalls = 3;
        balls[1] = 2;
        balls[2] = 2;
        balls[3] = 1;
 
        // Call the solve function
        Solve();
    }
}

Javascript

// JavaScript code for the above approach
 
// Number of balls
let numBalls = 3;
 
// Modulo for calculations
const mod = 1e9 + 7;
 
// Array to store the number of balls of each color
let balls = new Array(1200);
 
// Variables for loop indices
let i, j;
 
// Variable to store the sum of balls
let sumBalls = 0;
 
// Variable to store the answer
let numWays = 1;
 
// 2D array to store the binomial coefficients
let binomialCoefficients = new Array(1200).fill(0).map(() => new Array(1200).fill(0));
 
// Function to calculate binomial coefficients
function calculateBinomialCoefficients() {
    binomialCoefficients[0][0] = 1;
 
    for (i = 1; i <= 1005; ++i) {
        for (j = 0; j <= 1005; ++j) {
            binomialCoefficients[i][j] = (binomialCoefficients[i - 1][j] + ((j > 0) ? binomialCoefficients[i - 1][j - 1] : 0)) % mod;
        }
    }
}
 
// Function to solve the problem
function solve() {
    // Calculate all binomial coefficients
    calculateBinomialCoefficients();
 
    // Calculate the number of ways
    for (i = 1; i <= numBalls; ++i) {
        if (i > 1) {
            numWays = (numWays * binomialCoefficients[sumBalls + balls[i] - 1][balls[i] - 1]) % mod;
        }
        sumBalls += balls[i];
    }
 
    // Print the number of ways
    console.log(numWays);
}
 
// Set static input
balls[1] = 2;
balls[2] = 2;
balls[3] = 1;
 
// Call the solve function
solve();
 
// This code is contributed by Abhinav Mahajan (abhinav_m22)

Output

3

Time Complexity: O(n^2)
Auxiliary Space: O(n^2)


 


Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Find the number of ways in which groups can leave the lift (Rahul and The Lift) Find the number of ways in which groups can leave the lift (Rahul and The Lift)
Stars and Bars Algorithms for Competitive Programming Stars and Bars Algorithms for Competitive Programming
Count Weird Triplets Count Weird Triplets
Number of ways to Color the Boxes Number of ways to Color the Boxes
Count ways to traverse all N cities when each city is traversed K times Count ways to traverse all N cities when each city is traversed K times

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje