2151. Maximum Good People Based on Statements

There are two types of persons:

• The good person: The person who always tells the truth.
• The bad person: The person who might tell the truth and might lie.

You are given a 0-indexed 2D integer array statements of size n x n that represents the statements made by n people about each other. More specifically, statements[i][j] could be one of the following:

• 0 which represents a statement made by person i that person j is a bad person.
• 1 which represents a statement made by person i that person j is a good person.
• 2 represents that no statement is made by person i about person j.

Additionally, no person ever makes a statement about themselves. Formally, we have that statements[i][i] = 2 for all 0 <= i < n.

Return the maximum number of people who can be good based on the statements made by the n people.

• Time : O(2^n * n^2)
• Space : O(1)

class Solution {
    bool verify(int mask, vector<vector<int>>& st) {
        for(int i = 0; i < st.size(); i++) {
            if(mask & (1<<i)) {
                for(int j = 0; j < st.size(); j++) {
                    if(st[i][j] == 2) continue;
                    if(st[i][j] == 1 and (mask & (1<<j))) continue;
                    if(st[i][j] == 0 and !(mask & (1<<j))) continue;
                    return false;
                }
            }
        }
        return true;
    }
public:
    int maximumGood(vector<vector<int>>& statements) {
        int res = 0, n = statements.size(), ma = (1<<n);
        for(int mask = 1; mask < ma; mask++) {
            int cnt = __builtin_popcount(mask);
            if(cnt > res and verify(mask, statements)) {
                res = max(res, cnt);
            }
        }
        return res;
    }
};