Header Ads Widget

Team Formation | codechef solution

A programming competition will be held in Chef's city which only accepts teams of size 2. At least one person in a team should know a programming language and at least one person should know about the English language. It is possible that one person in a team knows both programming and the English language. Then the qualification of the other teammate is not important i.e. he may or may not know programming and English. Now Chef has  students and wants to send maximum number of teams to the competition.

You are given an integer  and two binary strings  and  of length = '1' denotes that the  student knows a programming language, and = '0' denotes otherwise; similarly, = '1' denotes that the  student knows English language, and = '0' denotes otherwise. Determine the maximum number of teams Chef can form.

Input Format

  • The first line of input contains a single integer  denoting the number of test cases. The description of  test cases follows.
  • Each test case contains 3 lines of input.
  • The first line of each test case contains an integer .
  • The second line of each test case contains a string .
  • The last line of each test case contains a string .

Output Format

For each test case, print a single line containing one integer - the maximum number of teams that Chef can form.

Constraints

  • 11000
  • 1100
  •  and  contains only characters '0' and '1'

Sample 1:

Input
Output
4
3
101
001
4
1010
0110
3
000
110
2
10
11

1
2
0
1

Explanation:

Test case 1: The third student can team up with any other students as he knows both programming and English.

Test case 2: The first two students make a team and the last two students make another team.

Test case 3: No student knows how to program, hence there is no way to make a team.

 Code(C++):-

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int Q,N;
    cin >> Q;
    
    while (Q--)
    {
     cin >> N;
     string s,t,dat;
     int ones{},twos{},threes{},fours{},pairs{},x,y;
    
     cin >> s >> t;
    
     for (int i=0;i<N;++i)
     {
     if(s[i]=='0' && t[i]=='0')
     ++ones;
     else if(s[i]=='1' && t[i]=='0')
     ++twos;
     else if(s[i]=='0' && t[i]=='1')
     ++threes;
     else
     ++fours;
     }
    
    
    
     if(ones<=fours)
     {
     x = (fours-ones);
     y = abs(twos-threes);
     pairs=ones+min(twos,threes)+min(x,y)+(x>y ? (x-y)/2 : 0);
     }
    
     else
     {
     pairs=fours+min(twos,threes);
     }
    
     cout << pairs <<"\n";
    }
    return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int t;
        t= in.nextInt();
        while(t-- > 0){
         int n;
         n=in.nextInt();
         String s= in.next();
         String s1= in.next();
         int count=0, count1=0;
         for(int i=0;i<n;i++){
         if(s.charAt(i) == '1' ){
         count++;
         }
         if(s1.charAt(i) == '1'){
         count1++;
         }
         }
         int ans= Math.min(n/2,Math.min(count,count1));
         System.out.println(ans);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Post a Comment

0 Comments