Given n instance of item A and m instance of item B. Find the maximum number of groups of size 3 that can be formed using these items such that all groups contain items of both types, i.e., a group should not have either all items of type A or all items of type B.
The total number of items of type A in the formed groups must be less than or equal to n.
The total number of items of type B in the formed groups must be less than or equal to m.
Examples :
Input : n = 2 and m = 6.
Output : 2
In group 1, one item of type A and two items of
type B. Similarly, in the group 2, one item of
type A and two items of type B.
We have used 2 (<= n) items of type A and 4 (<= m)
items of type B.
Input : n = 4 and m = 5.
Output : 3
In group 1, one item of type A and two items of type B.
In group 2, one item of type B and two items of type A.
In group 3, one item of type A and two items of type B.
We have used 4 (<= n) items of type A and 5 (<= 5)
items of type B.
Observation:
1. There will be n groups possible if m >= 2n. Or there will be m groups possible, if n >= 2m.
2. Suppose n = 3 and m = 3, so one instance of item A will make a group with the two instance of item B and one instance of item B will make a group with the two instance of item A. So, maximum two groups are possible. So find the total number of such conditions with given n and m by dividing m and m by 3. After this, there can be 0, 1, 2 instances of each type can be left. For finding the number of groups for the left instances:
a) If n = 0 or m = 0, 0 group is possible.
b) If n + m >= 3, only 1 group is possible.
Algorithm for solving this problem:
1. If n >= 2m, maximum number of groups = n.
2. Else if m >= 2n, maximum number of groups = m.
3. Else If (m + n) % 3 == 0, maximum number of group = (m + n)/3;
4. Else maximum number of group = (n + m)/3. And set n = n%3 and m = m%3.
a) If n != 0 && m != 0 && (n + m) >= 3, add one to maximum number of groups.
Below is the implementation of the above idea :
C++
#include<bits/stdc++.h>
using namespace std;
int maxGroup(int n, int m)
{
if (n >= 2 * m)
return n;
if (m >= 2 * n)
return m;
if ((m + n) % 3 == 0)
return (m + n)/3;
int ans = (m + n)/3;
m %= 3;
n %= 3;
if (m && n && (m + n) >= 3)
ans++;
return ans;
}
int main()
{
int n = 4, m = 5;
cout << maxGroup(n, m) << endl;
return 0;
}
|
Java
import java.io.*;
public class GFG{
static int maxGroup(int n, int m)
{
if (n >= 2 * m)
return n;
if (m >= 2 * n)
return m;
if ((m + n) % 3 == 0)
return (m + n) / 3;
int ans = (m + n) / 3;
m %= 3;
n %= 3;
if (m > 0 && n > 0 && (m + n) >= 3)
ans++;
return ans;
}
static public void main (String[] args)
{
int n = 4, m = 5;
System.out.println(maxGroup(n, m));
}
}
|
Python3
def maxGroup(n, m):
if n >= 2 * m:
return n
if m >= 2 * n:
return m
if (m + n) % 3 == 0:
return (m + n) // 3
ans = (m + n) // 3
m = m % 3
n = n % 3
if m and n and (m + n) >= 3:
ans += 1
return ans
n, m = 4, 5
print(maxGroup(n, m))
|
C#
using System;
public class GFG{
static int maxGroup(int n, int m)
{
if (n >= 2 * m)
return n;
if (m >= 2 * n)
return m;
if ((m + n) % 3 == 0)
return (m + n) / 3;
int ans = (m + n) / 3;
m %= 3;
n %= 3;
if (m > 0 && n > 0 && (m + n) >= 3)
ans++;
return ans;
}
static public void Main ()
{
int n = 4, m = 5;
Console.WriteLine(maxGroup(n, m));
}
}
|
Javascript
<script>
function maxGroup(n, m)
{
if (n >= 2 * m)
return n;
if (m >= 2 * n)
return m;
if ((m + n) % 3 == 0)
return (m + n) / 3;
let ans = (m + n) / 3;
m %= 3;
n %= 3;
if (m > 0 && n > 0 && (m + n) >= 3)
ans++;
return ans;
}
let n = 4, m = 5;
document.write(maxGroup(n, m));
</script>
|
PHP
<?php
function maxGroup($n, $m)
{
if ($n >= 2 * $m)
return n;
if ($m >= 2 * $n)
return m;
if ((($m + $n) % 3) == 0)
return ($m + $n) / 3;
$ans = ($m + $n) / 3;
$m %= 3;
$n %= 3;
if ($m && $n && ($m + $n) >= 3)
$ans++;
return $ans;
}
$n = 4; $m = 5;
echo maxGroup($n, $m) ;
?>
|
Time Complexity: O(1)
Auxiliary Space: O(1)
Using dynamic programing in python:
We can also solve this problem using dynamic programming. We can define a two-dimensional table dp[i][j] where i represents the number of items of type A used so far, and j represents the number of items of type B used so far. The value of dp[i][j] represents the number of groups that can be formed using i items of type A and j items of type B. We can fill this table iteratively by considering each item of type A and type B and updating the corresponding entries in the table
C++
#include <iostream>
#include <vector>
using namespace std;
int count_groups(int n, int m)
{
vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i > 0 && j >= 2) {
dp[i][j] += dp[i - 1][j - 2];
}
if (j > 0 && i >= 2) {
dp[i][j] += dp[i - 2][j - 1];
}
}
}
int count = 2;
for (int k = 1; k <= min(n, m / 2); k++) {
count += dp[k][m - 2 * k];
}
return count;
}
int main()
{
int n = 2, m = 6;
cout << count_groups(n, m) << endl;
return 0;
}
|
Java
import java.util.Arrays;
class GFG {
static int countGroups(int n, int m) {
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i > 0 && j >= 2) {
dp[i][j] += dp[i - 1][j - 2];
}
if (j > 0 && i >= 2) {
dp[i][j] += dp[i - 2][j - 1];
}
}
}
int count = 2;
for (int k = 1; k <= Math.min(n, m / 2); k++) {
count += dp[k][m - 2 * k];
}
return count;
}
public static void main(String[] args) {
int n = 2, m = 6;
System.out.println(countGroups(n, m));
}
}
|
Python3
def count_groups(n, m):
dp = [[0]*(m+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n+1):
for j in range(m+1):
if i > 0 and j >= 2:
dp[i][j] += dp[i-1][j-2]
if j > 0 and i >= 2:
dp[i][j] += dp[i-2][j-1]
count = 2
for k in range(1, min(n, m//2)+1):
count += dp[k][m-2*k]
return count
n = 2
m = 6
print(count_groups(n, m))
|
C#
using System;
class Program
{
static int CountGroups(int n, int m)
{
int[,] dp = new int[n + 1, m + 1];
dp[0, 0] = 1;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
if (i > 0 && j >= 2)
{
dp[i, j] += dp[i - 1, j - 2];
}
if (j > 0 && i >= 2)
{
dp[i, j] += dp[i - 2, j - 1];
}
}
}
int count = 2;
for (int k = 1; k <= Math.Min(n, m / 2); k++)
{
count += dp[k, m - 2 * k];
}
return count;
}
static void Main(string[] args)
{
int n = 2, m = 6;
Console.WriteLine(CountGroups(n, m));
}
}
|
Javascript
function countGroups(n, m) {
let dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
dp[0][0] = 1;
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
if (i > 0 && j >= 2) {
dp[i][j] += dp[i - 1][j - 2];
}
if (j > 0 && i >= 2) {
dp[i][j] += dp[i - 2][j - 1];
}
}
}
let count = 2;
for (let k = 1; k <= Math.min(n, Math.floor(m / 2)); k++) {
count += dp[k][m - 2 * k];
}
return count;
}
let n = 2, m = 6;
console.log(countGroups(n, m));
|
Time complexity:
The time complexity of this program is O(nm), where n and m are the input parameters. This is because we create a 2D matrix of size (n+1) x (m+1) using nested loops, and then perform two more nested loops over the range (1, min(n, m//2)+1), resulting in an overall time complexity of O(nm).
Space complexity:
The space complexity of this program is O(nm), since we create a 2D matrix of size (n+1) x (m+1) to store intermediate results. The size of this matrix is proportional to the product of n and m, so the space complexity is O(nm). The other variables created in this program are of constant size, so they do not contribute significantly to the overall space complexity.