Find the number of ways to fill the buckets with balls
Given N buckets and the infinite number of balls. The maximum capacity of each bucket is given in an array capacity[], the task is to find the number of ways to fill the buckets with balls such that each bucket has at least 1 ball and all the buckets have a distinct number of balls in them. Return your answer to the modulo 10^9+7.
Examples:
Input: N = 1, capacity[] = {6}
Output: 6
Explanation: Since there is only one bucket. It may hold any number of balls ranging from 1 to 6.Input: N = 2, capacity[] = {5, 8}
Output: 35
Explanation: If the first bucket has 1 ball in it then the second bucket cant have 1 ball, so the second bucket has 8 – 1 = 7 choices. So, the first bucket has 5 choices, and for each choice, the second bucket has 7 choices. So total there are 35 ways.
Approach: This can be solved with the following idea:
We have to keep each bucket with a distinct number of balls. If 1st bucket contains x number of balls then buckets from 2nd to last can’t have x number of balls in them, which means they have their (capacity – 1) choice. If observe carefully, we can find i’th bucket has (capacity of i’th bucket – i – 1) choices. Now we have to arrange the buckets in a way such that the capacity of the bucket is greater than (i – 1).
Steps involved in the implementation of code:
- Sort the capacity vector.
- ans = (ans * (capacity[i]-i)) % mod;
- return ans.
Below is the implementation of the above approach:
// C++ Implementation of code
#include <bits/stdc++.h>
using namespace std;
// Function to count total number of ways
int totalWays(int n, vector<int> capacity)
{
long long int mod = 1000000007;
// Sort the array capacity
sort(capacity.begin(), capacity.end());
bool flag = false;
long long int ans = 1;
// Iterate from last element
for (int i = n - 1; i >= 0; i--) {
if (capacity[i] < i) {
flag = true;
break;
}
else
ans = (ans % mod * (capacity[i] - i) % mod)
% mod;
}
if (flag)
return 0;
// Return ans
return int(ans);
}
// Driver code
int main()
{
vector<int> capacity = { 5, 8 };
int n = 2;
// Function call
int ans = totalWays(n, capacity);
cout << ans;
return 0;
}
import java.util.*;
public class Main {
// Function to count total number of ways
static int totalWays(int n, List<Integer> capacity) {
long mod = 1000000007;
// Sort the array capacity
Collections.sort(capacity);
boolean flag = false;
long ans = 1;
// Iterate from last element
for (int i = n - 1; i >= 0; i--) {
if (capacity.get(i) < i) {
flag = true;
break;
} else
ans = (ans % mod * (capacity.get(i) - i) % mod) % mod;
}
if (flag)
return 0;
// Return ans
return (int) ans;
}
// Driver code
public static void main(String[] args) {
List<Integer> capacity = new ArrayList<Integer>();
capacity.add(5);
capacity.add(8);
int n = 2;
// Function call
int ans = totalWays(n, capacity);
System.out.println(ans);
}
}
//This code is contributed by chinmaya121221
# Python implementation of code
# Function to count total number of ways
def totalWays(n, capacity):
mod = 1000000007
# Sort the array capacity
capacity.sort()
flag = False
ans = 1
# Iterate from last element
for i in range(n - 1, -1, -1):
if capacity[i] < i:
flag = True
break
else:
ans = (ans % mod * (capacity[i] - i) % mod) % mod
if flag:
return 0
# Return ans
return ans
# Driver code
if __name__ == '__main__':
capacity = [5, 8]
n = 2
# Function call
ans = totalWays(n, capacity)
print(ans)
# This code is contributed by Susobhan Akhuli
using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
public static int TotalWays(int n, List<int> capacity)
{
long mod = 1000000007;
// Sort the List capacity
capacity.Sort();
bool flag = false;
long ans = 1;
// Iterate from last element
for (int i = n - 1; i >= 0; i--) {
if (capacity[i] < i) {
flag = true;
break;
}
else
ans = (ans % mod * (capacity[i] - i) % mod)
% mod;
}
if (flag)
return 0;
// Return ans
return (int)ans;
}
public static void Main()
{
List<int> capacity = new List<int>{ 5, 8 };
int n = 2;
// Function call
int ans = TotalWays(n, capacity);
Console.WriteLine(ans);
}
}
// This code is contributed by Prajwal Kandekar
// Function to count total number of ways
function totalWays(n, capacity) {
const mod = 1000000007;
// Sort the array capacity
capacity.sort((a, b) => a - b);
let flag = false;
let ans = 1;
// Iterate from last element
for (let i = n - 1; i >= 0; i--) {
if (capacity[i] < i) {
flag = true;
break;
} else {
ans = ((ans % mod) * ((capacity[i] - i) % mod)) % mod;
}
}
if (flag)
return 0;
// Return ans
return ans;
}
// Driver code
const capacity = [5, 8];
const n = 2;
// Function call
const ans = totalWays(n, capacity);
console.log(ans);
Output
35
Time Complexity: O(n*log(n))
Auxiliary Space: O(1).