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 S
Examples:
Input: C0 = 2, C1 = 4, C2 = 1
Output: 4
Explanation: 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 = 0
Output: 250
Approach: 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.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;int maxGroup(int c0, int c1, int c2){ // Initializing to store maximum number of groups int maxAns = 0; // Adding C0 maxAns += c0; // Taking Minimum of c1, c2 as minimum number of // pairs must be minimum of c1, c2 int k = min(c1, c2); maxAns += k; // If there is any remaining element in c1 or c2 // then it must be the absolute difference of c1 and // c2 and dividing it by 3 to make it one pair maxAns += abs(c1 - c2) / 3; return maxAns;}int main(){ int C0 = 2, C1 = 4, C2 = 1; cout << maxGroup(C0, C1, C2); return 0;}// This code is contributed by maddler |
Java
// Java program for above approachimport java.io.*;class GFG { // Function to calculate maximum number of groups public static int maxGroup(int c0, int c1, int c2) { // Initializing to store maximum number of groups int maxAns = 0; // Adding C0 maxAns += c0; // Taking Minimum of c1, c2 as minimum number of // pairs must be minimum of c1, c2 int k = Math.min(c1, c2); maxAns += k; // If there is any remaining element in c1 or c2 // then it must be the absolute difference of c1 and // c2 and dividing it by 3 to make it one pair maxAns += Math.abs(c1 - c2) / 3; return maxAns; } // Driver Code public static void main(String[] args) { // Given Input int C0 = 2, C1 = 4, C2 = 1; // Function Call System.out.println(maxGroup(C0, C1, C2)); }} |
Python3
# python 3 program for above approachdef maxGroup(c0, c1, c2): # Initializing to store maximum number of groups maxAns = 0 # Adding C0 maxAns += c0 # Taking Minimum of c1, c2 as minimum number of # pairs must be minimum of c1, c2 k = min(c1, c2) maxAns += k # If there is any remaining element in c1 or c2 # then it must be the absolute difference of c1 and # c2 and dividing it by 3 to make it one pair maxAns += abs(c1 - c2) // 3 return maxAns # Driver codeif __name__ == '__main__': C0 = 2 C1 = 4 C2 = 1 print(maxGroup(C0, C1, C2)) # This code is contributed by ipg2016107. |
C#
// C# program for above approachusing System;class GFG{ // Function to calculate maximum number of groups public static int maxGroup(int c0, int c1, int c2){ // Initializing to store maximum number // of groups int maxAns = 0; // Adding C0 maxAns += c0; // Taking Minimum of c1, c2 as minimum number // of pairs must be minimum of c1, c2 int k = Math.Min(c1, c2); maxAns += k; // If there is any remaining element // in c1 or c2 then it must be the // absolute difference of c1 and c2 // and dividing it by 3 to make it one pair maxAns += Math.Abs(c1 - c2) / 3; return maxAns;}// Driver Codestatic public void Main(){ // Given Input int C0 = 2, C1 = 4, C2 = 1; // Function Call Console.WriteLine(maxGroup(C0, C1, C2));}}// This code is contributed by maddler |
Javascript
<script> // JavaScript program for the above approach; function maxGroup(c0, c1, c2) { // Initializing to store maximum number of groups let maxAns = 0; // Adding C0 maxAns += c0; // Taking Minimum of c1, c2 as minimum number of // pairs must be minimum of c1, c2 let k = Math.min(c1, c2); maxAns += k; // If there is any remaining element in c1 or c2 // then it must be the absolute difference of c1 and // c2 and dividing it by 3 to make it one pair maxAns += Math.abs(c1 - c2) / 3; return maxAns; } let C0 = 2, C1 = 4, C2 = 1; document.write(maxGroup(C0, C1, C2)); // This code is contributed by Potta Lokesh </script> |
Output:
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
