Ways to Arrange Balls

Hard
0/120
Average time to solve is 40m
profile
Contributed by
21 upvotes
Asked in companies
GeeksforGeeksDavis SoftwareFord Motor Company

Problem statement

Given ‘a’ balls of type ‘A’, ‘b’ balls of type ‘B’ and ‘c’ balls of type ‘C’. You need to find the total number of ways to arrange the balls in a straight line such that adjacent balls are of different types.

In other words, find the total ways to arrange the given balls in such a way that no two balls of the same type are adjacent.

For Example : 
Suppose we have 2 balls of type ‘A’, 1 ball of type ‘B’ and 1 ball of type ‘C’, following are the ways to arrange them in the required fashion. 
ABCA
ABAC 
ACBA 
ACAB 
BACA 
CABA 
Hence, there is a total of six ways.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test contains three space-separated positive integers a, b, c, denoting the number of balls of type ‘A’, ‘B’, and ‘C’ respectively.
Output Format : 
For each test case, print the total ways to arrange the balls such that adjacent balls are of a different type in a single line.

Print the output of each test case in a separate line.
Note : 
You don’t have to print anything, it has already been taken care of. Just complete the function. 

If there is no way, return 0.
Constraints : 
1 <= T <= 100
0 <= a, b, c <= 15

Time limit: 1 sec
Sample Input 1 :
2
1 2 1
1 1 1
Sample Output 1 :
6
6
Explanation of Sample Input 1 :
Test Case 1: We have one ball of type A, two balls of type B and one ball of type C. All the possible arrangements such that no two adjacent balls are of the same type are shown below. 
ABCB
BACB
BABC
BCAB
BCBA 
CBAB

These are all the six possible arrangements.

Test Case 2: We have 1 ball of each type. All the possible arrangements are - 
ABC
ACB
BAC
BCA
CAB
CBA

These are all six possible arrangements.
Sample Input 2 :
2
4 5 3
8 3 1
Sample Output 2 :
588
0
Hint

Can you do this recursively? 

Approaches (3)
Recursion

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion. We will keep track of the next ball we want to add in the line. Initially, we have three options, to begin with. We can start by adding A or B or C. After that, at each step, we have two options. We can find the number of ways to make the required arrangements from the remaining balls. 

 

Algorithm:  

 

  • We will call a recursive function ‘helper’ that takes all the three integers a, b, c, and a variable ‘nextBall’ as arguments and returns us the total number of ways to arrange the balls in the required fashion.
  • Initialize a variable called ‘totalWays’ by 0.
  • Call helper function for all possible value of ‘nextBall’ and store the answer in ‘totalWays’, i.e. totalWays = helper(a, b, c, 0) + helper(a, b, c, 1) + helper(a, b, c, 2).
  • The algorithm for the helper function will be as follows: 
    Int helper(a, b, c, nextBall):
    A. If ‘a’ or ‘b’ or ‘c’ becomes less than 0, return 0 as we can’t have an arrangement in this case.
    B. Now check,
    • if the ‘nextBall’ is 0, means we have to add a ball of type A.
      • If ‘a’ is 1 and ‘b’ and ‘c’ are 0, return 1 as we have found an arrangement.
      • Else return helper(a - 1, b,  c, 1) + helper(a - 1, b, c, 2).
    • If the ‘nextBall’ is 1, means we have to add a ball of type B.
      • If ‘b' is 1 and ‘a’ and ‘c’ are 0, return 1 as we have found an arrangement.
      • Else return helper(a , b - 1, c, 0) + helper(a, b - 1, c, 2).
    • If the ‘nextBall’ is 2, means we have to add a ball of type C.
      • If ‘c’ is 1 and ‘a’ and ‘b’ are 0, return 1 as we have found an arrangement.
      • Else return helper(a, b, c - 1, 0) + helper(a, b, c - 1, 1).
  • Return the ‘totalWays’.
Time Complexity

O(2^(min(a,b,c)), where ‘a’, ‘b’, ‘c’ are the number of balls of type ‘A’, ‘B’, and ‘C’ respectively.

 

As we are making three calls to the helper function whose time complexity is O(2^(min(a, b, c)).

Space Complexity

O(min(a, b, c)), where a, b, c denoting the number of balls of type ‘A’, ‘B’, and ‘C’ respectively.

 

This is the recursion stack space used by the algorithm.

Code Solution
(100% EXP penalty)
Ways to Arrange Balls
Full screen
Console