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.
Contact Us