HackerEarth Samu and her Birthday Party problem solution

In this HackerEarth Samu and her Birthday Party problem solution, Samu's Birthday is near so she had started planning a party for all of her friends. Being a kind and caring girl she calls each of her friends and asks for his/her favorite dish. Now each friend has their own liking/disliking for different dishes.

A friend can only like or dislike a dish it means if we are having three dishes 1, 2, 3 then if a friend says that he likes Dishes 1 and 2 then it's obvious that he dislikes Dish 3. So for each friend we are given a string of 1 and 0 where 1 shows that this person likes this particular dish.

Now we are given that Samu has N friends and a total of K dishes available to make her menu. Now Samu doesn't want to make any of her friends unhappy, After all, it's her birthday.

So she got confused about what dishes to count on the menu and calls you for help. You need to find the count of minimum dishes to order so that all of her N friends are happy which means everyone has at least one dish to eat at the party.

HackerEarth Samu and her Birthday Party problem solution.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector<string> friends;
        for(int i=0;i<n;i++){
            string x;
            cin>>x;
            friends.push_back(x);
        }
        vector<int> mask;
        for(int i=0;i<n;i++){
            int a=0;
            for(int j=0;j<k;j++){
                if(friends[i][j]=='1')
                {
                    a=a | (1<<(k-1-j));
                }
            }
            mask.push_back(a);
        }
        int ans=k;
        for(int i=1;i<(1<<k);i++){
            bool isPossible=true;
            for(int j=0;j<n;j++){
                if((mask[j] & i)==0)
                {
                    isPossible=false;
                }
            }
            if(isPossible==true){
                int counter=0;
                for(int m=0;m<k;m++){
                    if((1<<m)&i)
                    {
                        counter++;
                    }
                }
                ans=min(ans,counter);
            }
        }
        cout<<ans<<"\n";
    }
}

Second solution

#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define repi(i,n) for(int i=0; i<(int)n;i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define sortv(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
#define DRT()  int t; cin>>t; while(t--)
#define TRACE
using namespace std;


#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector< PII > VPII;
int A[500];
int N,K; 

bool f(int mask)
{
    for(int i=0; i<N;i++)
        if((mask&A[i])==0)return false;
    return true;
}

int main()
{
    DRT()
    {
        cin>>N>>K;
        assert(N>0 and N<=500);
        assert(K>0 and K<=10);
        repi(i,N)
        {
            A[i] = 0;
            string s; cin>>s; 
            assert(SZ(s)==K);
            repi(j,K) 
                A[i] = 2*A[i] + (s[j]-'0');
        }
        int ans = K+1;
        repi(i,(1<<K))
        {
            if(f(i)) ans  = min(ans,__builtin_popcount(i));
        }
        assert(ans!=K+1);
        cout<<ans<<endl;
    }
    return 0;
}