Wednesday, 27 Oct 2021

# Maximize count of groups from given 0s, 1s and 2s with sum divisible by 3

Given three integers, C0, C1 and C2 frequencies of 0s, 1s and 2s in a group S. The task is to find the maximum number of groups having the sum divisible by 3, the condition is the sum(S) is divisible by 3 and the union of all groups must be equal to SExamples:Input: C0 = 2, C1 = 4, C2 = 1Output: 4Explanation: it can divide the group S = {0, 0, 1, 1, 1, 1, 2} into four groups {0}, {0}, {1, 1, 1}, {1, 2}. It can be proven that 4 is the maximum possible answer.Input: C0 = 250, C1 = 0, C2 = 0Output: 250Approach: This problem can be solved using the Greedy Algorithm. follow the steps given below to solve the problem.Initialize a variable maxAns, say 0, to store the maximum number of groups.Add C0 to maxAns, because every {0} can be a group such that the sum is divisible by 3.Initialize a variable k, say min(C1, C2), and add it to maxAns, because at least k, {1, 2} group can be created.Add abs(C1-C2) /3 to maxAns, it will contribution of the remaining 1s or 2s.Return maxAns.Below is the implementation of the above approach.Java  import java.io.*;  class GFG {          public static int maxGroup(int c0, int c1, int c2)    {                  int maxAns = 0;                  maxAns += c0;                          int k = Math.min(c1, c2);        maxAns += k;                                  maxAns += Math.abs(c1 – c2) / 3;          return maxAns;    }          public static void main(String[] args)    {                int C0 = 2, C1 = 4, C2 = 1;                  System.out.println(maxGroup(C0, C1, C2));    }}Time Complexity: O(1)Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.