Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks


Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks
There are 'a' balls of type A, 'b' balls of type B and 'c' balls of type C. Using the balls we want to create a straight colorful line such that no two balls of same type are adjacent.
Input  : a = 1, b = 1, c = 0
Output : 2
There are only two arrangements AB and BA

Input  : a = 1, b = 1, c = 1
Output : 6
There are only six arrangements ABC, BAC, 
BCA, CBA, ACB and CAB

We can observe that there are many subproblems being solved again and again so the problem can be solved using Dynamic Programming (DP). We can easily make memoization solution to this problem.
Time complexity : O(a*b*c)
Auxiliary Space : O(a*b*c*3)
// table to store to store results of subproblems
int dp[MAX][MAX][MAX][3];
 
// Returns count of arrangements where last placed ball is
// 'last'.  'last' is 0 for 'a', 1 for 'b' and 2 for 'c'
int countWays(int a, int b, int c, int last)
{
    // if number of balls of any color becomes less
    // than 0 the number of ways arrangements is 0.
    if (a<0 || b<0 || c<0)
        return 0;
 
    // If last ball required is of type A and the number
    // of balls of A type is 1 while number of balls of
    // other color is 0 the number of ways is 1.
    if (a==1 && b==0 && c==0 && last==0)
        return 1;
 
    // Same case as above for 'b' and 'c'
    if (a==0 && b==1 && c==0 && last==1)
        return 1;
    if (a==0 && b==0 && c==1 && last==2)
        return 1;
 
    // If this subproblem is already evaluated
    if (dp[a][b][last] != -1)
        return dp[a][b][last];
 
    // if last ball required is A and the number of ways is
    // the sum of number of ways to form sequence with 'a-1' A
    // balls, b B Balls and c C balls ending with B and C.
    if (last==0)
       dp[a][b]1[last] = countWays(a-1,b,c,1) + countWays(a-1,b,c,2);
 
    // Same as above case for 'b' and 'c'
    else if (last==1)
       dp[a][b]1[last] = countWays(a,b-1,c,0) + countWays(a,b-1,c,2);
    else //(last==2)
       dp[a][b]1[last] =  countWays(a,b,c-1,0) + countWays(a,b,c-1,1);
 
    return dp[a][b]1[last];
}

// Returns count of required arrangements
int countUtil(int a, int b, int c)
{
   // Initialize 'dp' array
   memset(dp, -1, sizeof(dp));
 
   // Three cases arise:
   return countWays(a, b, c, 0) +  // Last required balls is type A
          countWays(a, b, c, 1) +  // Last required balls is type B
          countWays(a, b, c, 2); // Last required balls is type C
}
The naive solution to this problem is a recursive solution. We recursively call for three cases
1) Last ball to be placed is of type A
2) Last ball to be placed is of type B
3) Last ball to be placed is of type C
// Returns count of arrangements where last placed ball is
// 'last'.  'last' is 0 for 'a', 1 for 'b' and 2 for 'c'
int countWays(int a, int b, int c, int last)
{
    // if number of balls of any color becomes less
    // than 0 the number of ways arrangements is 0.
    if (a<0 || b<0 || c<0)
        return 0;
 
    // If last ball required is of type A and the number
    // of balls of A type is 1 while number of balls of
    // other color is 0 the number of ways is 1.
    if (a==1 && b==0 && c==0 && last==0)
        return 1;
 
    // Same case as above for 'b' and 'c'
    if (a==0 && b==1 && c==0 && last==1)
        return 1;
    if (a==0 && b==0 && c==1 && last==2)
        return 1;
 
    // if last ball required is A and the number of ways is
    // the sum of number of ways to form sequence with 'a-1' A
    // balls, b B Balls and c C balls ending with B and C.
    if (last==0)
        return countWays(a-1,b,c,1) + countWays(a-1,b,c,2);
 
    // Same as above case for 'b' and 'c'
    if (last==1)
        return countWays(a,b-1,c,0) + countWays(a,b-1,c,2);
    if (last==2)
        return countWays(a,b,c-1,0) + countWays(a,b,c-1,1);
}
 
// Returns count of required arrangements
int countUtil(int a, int b, int c)
{
   // Three cases arise:
   return countWays(a, b, c, 0) +  // Last required balls is type A
          countWays(a, b, c, 1) +  // Last required balls is type B
          countWays(a, b, c, 2); // Last required balls is type C
}

Read full article from Ways to arrange Balls such that adjacent balls are of different types - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts