Leetcode 2151: Maximum Good People Based on Statements

Problem Description

#

Check out the full problem description

There are two types of people:

• 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.

Solution

#

The general approach I will take is to iterate over each possible configuration of good and bad people using bit manipulation.

Representing a configuration

#

Represent a possible configuration of n people using n bits.

• 1 = good person
• 0 = bad person

E.g. 1010 = People 1,3 are good. People 2,4 are bad.

Iterating over configurations

#

Naive approach

#

We can iterate over all the possible configurations, starting with all people lying, like so:

for(int config=0; config<(1<<n); config++){
    // check if the solution is valid
}

Improved approach

#

We first start by looking at configurations where everyone is good. We then stop looking when none of the remaining possible solutions can beat our current one.

For example, imagine we have five people, and found a configuration where 3 could be telling the truth (maxGood is 3), we need to find at least four 1’s (truthful bits) to find a better solution. In this example, if config<01111, then we can stop because config is decreasing, so it will never have four 1’s.

• initialise config = 111...1111
• stop searching when config < ..000111.. (ending in maxGood 1’s)

for(int config=(1<<n)-1; config >= (1<<(maxGood+1))-1; config--){
    // check if the solution is valid
}

Checking if a solution is valid

#

A solution is invalid when someone who is assumed to be truthful tells a lie. (Ignore what the liars say.)

Therefore, iterate over all the truthful people in a solution and check what they say matches our proposed solution.

bool configurationWorks = true;
// iterate over each person in the config
for(int j=0; j<n && configurationWorks; j++){
    if((config>>j)&1){
        // the current person is telling the truth
        for(int h=0; h<n; h++){
            // the accused is not what they are supposed to be
            // e.g. person j says person h is good when they are bad
            if(statements[j][h] != 2 && statements[j][h] != ((config>>h)&1)){
                configurationWorks = false;
                break;
            }
        }
    }
}

Setting the new Max Score

#

The number of good people in a configuration is the number of 1’s in the binary representation of config. There is already a function to do this called __builtin_popcount.

if(configurationWorks){
    maxGood = max(maxGood, __builtin_popcount(config));
}

Complexity

#

Time complexity: O(\(N^2 * 2^N\))

Space complexity: O(\(\sqrt{N}\))

Code

#

class Solution {
public:
    int maximumGood(const vector<vector<int>>& statements) {
        int n = statements.size();
        int maxGood = 0;
        // config has n bits. A 1 represents good, and a 0 represents bad
        for(int config=(1<<n)-1; config >= (1<<(maxGood+1))-1; config--){
            bool configurationWorks = true;
            // iterate over each person in the config
            for(int j=0; j<n && configurationWorks; j++){
                if((config>>j)&1){
                    // the current person is telling the truth
                    for(int h=0; h<n; h++){
                        // the accused is not what they are supposed to be
                        // e.g. person j says person h is good when they are bad
                        if(statements[j][h] != 2 && statements[j][h] != ((config>>h)&1)){
                            configurationWorks = false;
                            break;
                        }
                    }
                }
            }
            if(configurationWorks){
                maxGood = max(maxGood, __builtin_popcount(config));
            }
        }
        return maxGood;
    }
};