Count of ways to distribute N items among 3 people with one person receiving maximum
Given an integer N, the task is to find the total number of ways to distribute N among 3 people such that:
- Exactly one person gets the maximum number of items among all the 3 people.
- Each person gets at least 1 item.
Examples:
Input: N = 5
Output: 3
Explanation:
3 ways to distribute the item among 3 people are {1, 1, 3}, {1, 3, 1} and {3, 1, 1}.
Distributions like {1, 2, 2} or {2, 1, 2} are not valid as two persons are getting the maximum.
Input: N = 10
Output: 33
Explanation:
For the Input N = 10 there are 33 ways of distribution.
Approach:
To solve the problem mentioned above, we have to observe that if N < 4, then such a distribution is not possible.
For all values of N ? 4, follow the steps to solve the problem:
- Total no of ways to distribute N items among 3 people is given by (N – 1) * (N – 2) / 2.
- Initialize a variable s = 0 which stores the count of ways the distribution is not possible.
- Iterate two nested loops, where i ranges between [2, N – 3] and j ranging upto i:
- For each iteration, check if N = 2 * i + j, that is 2 persons can receive the maximum number of elements
- If so, then increment s by 1. If N is divisible by 3, update s by 3 * s + 1. Otherwise, update to 3 * s.
- Finally, return ans – s as the total number of ways to distribute N items among three people.
Below is the implementation of the above approach:
C++
// C++ program to find the number // of ways to distribute N item // among three people such // that one person always gets // the maximum value #include <bits/stdc++.h> using namespace std; // Function to find the number // of ways to distribute N // items among 3 people int countWays( int N) { // No distribution // possible if (N < 4) return 0; // Total number of ways to // distribute N items // among 3 people int ans = ((N - 1) * (N - 2)) / 2; // Store the number of // distributions which // are not possible int s = 0; for ( int i = 2; i <= N - 3; i++) { for ( int j = 1; j < i; j++) { // Count possibilities // of two persons // receiving the // maximum if (N == 2 * i + j) s++; } } // If N is divisible by 3 if (N % 3 == 0) s = 3 * s + 1; else s = 3 * s; // Return the final // count of ways // to distribute return ans - s; } // Driver Code int main() { int N = 10; cout << countWays(N); return 0; } |
Java
// Java program to find the number // of ways to distribute N item // among three people such // that one person always gets // the maximum value class GFG{ // Function to find the number // of ways to distribute N // items among 3 people static int countWays( int N) { // No distribution // possible if (N < 4 ) return 0 ; // Total number of ways to // distribute N items // among 3 people int ans = ((N - 1 ) * (N - 2 )) / 2 ; // Store the number of // distributions which // are not possible int s = 0 ; for ( int i = 2 ; i <= N - 3 ; i++) { for ( int j = 1 ; j < i; j++) { // Count possibilities // of two persons // receiving the // maximum if (N == 2 * i + j) s++; } } // If N is divisible by 3 if (N % 3 == 0 ) s = 3 * s + 1 ; else s = 3 * s; // Return the final // count of ways // to distribute return ans - s; } // Driver Code public static void main(String[] args) { int N = 10 ; System.out.println(countWays(N)); } } // This code is contributed by rock_cool |
Python3
# Python3 program to find the number # of ways to distribute N item # among three people such # that one person always gets # the maximum value # Function to find the number # of ways to distribute N # items among 3 people def countWays(N): # No distribution # possible if (N < 4 ): return 0 # Total number of ways to # distribute N items # among 3 people ans = ((N - 1 ) * (N - 2 )) / / 2 # Store the number of # distributions which # are not possible s = 0 for i in range ( 2 , N - 2 , 1 ): for j in range ( 1 , i, 1 ): # Count possibilities # of two persons # receiving the # maximum if (N = = 2 * i + j): s + = 1 # If N is divisible by 3 if (N % 3 = = 0 ): s = 3 * s + 1 else : s = 3 * s # Return the final # count of ways # to distribute return ans - s # Driver Code N = 10 print (countWays(N)) # This code is contributed by sanjoy_62 |
C#
// C# program to find the number // of ways to distribute N item // among three people such // that one person always gets // the maximum value using System; class GFG{ // Function to find the number // of ways to distribute N // items among 3 people static int countWays( int N) { // No distribution // possible if (N < 4) return 0; // Total number of ways to // distribute N items // among 3 people int ans = ((N - 1) * (N - 2)) / 2; // Store the number of // distributions which // are not possible int s = 0; for ( int i = 2; i <= N - 3; i++) { for ( int j = 1; j < i; j++) { // Count possibilities // of two persons // receiving the // maximum if (N == 2 * i + j) s++; } } // If N is divisible by 3 if (N % 3 == 0) s = 3 * s + 1; else s = 3 * s; // Return the final // count of ways // to distribute return ans - s; } // Driver Code public static void Main() { int N = 10; Console.Write(countWays(N)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program to find the number // of ways to distribute N item // among three people such // that one person always gets // the maximum value // Function to find the number // of ways to distribute N // items among 3 people function countWays(N) { // No distribution // possible if (N < 4) return 0; // Total number of ways to // distribute N items // among 3 people let ans = ((N - 1) * (N - 2)) / 2; // Store the number of // distributions which // are not possible let s = 0; for (let i = 2; i <= N - 3; i++) { for (let j = 1; j < i; j++) { // Count possibilities // of two persons // receiving the // maximum if (N == 2 * i + j) s++; } } // If N is divisible by 3 if (N % 3 == 0) s = 3 * s + 1; else s = 3 * s; // Return the final // count of ways // to distribute return ans - s; } let N = 10; document.write(countWays(N)); </script> |
Output:
33
Time complexity: O(N2)
Auxiliary Space: O(1)