We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Good People Based on Statements

Number: 2272

Difficulty: Hard

Paid? No

Companies: Oracle, TuSimple

Problem Description

Given n people with statements about each other where a good person always tells the truth and a bad person may lie or tell the truth, determine the maximum possible number of good people that can exist such that all statements made by assumed good people are consistent.

Key Insights

  • Enumerate every possible assignment of good (truth-tellers) and bad (potential liars) using bit masking.
  • For every assumed assignment, only consider the statements from people assumed as good.
  • For a person i assumed good, their statement about person j must be consistent: if statements[i][j] == 1 then j must be good; if it equals 0 then j must be bad.
  • Since n is at most 15, a brute-force approach over all 2^n assignments (maximum of 32768 possibilities) is feasible.

Space and Time Complexity

Time Complexity: O(2^n * n^2) – we iterate through all possible 2^n assignments and, for each, check up to n people making n statements each. Space Complexity: O(n) – extra space used for iteration and helper variables.

Solution

We solve the problem by using bit manipulation to iterate over each possible configuration (mask) that assigns each person as either good (bit set) or bad (bit not set). For each configuration, we verify if it is valid by ensuring that for every person i assumed good (bit is set), their statements about every other person j align with the assumed configuration: statement 1 must correspond to j being good; statement 0 must correspond to j being bad; statements with value 2 can be ignored. We track the maximum count of good people across all valid configurations.

Code Solutions

# Python solution for Maximum Good People Based on Statements

class Solution:
    def maximumGood(self, statements):
        n = len(statements)
        max_good = 0
        # iterate over each possible mask configuration (i.e., every assignment)
        for mask in range(1 << n):
            valid = True
            # Check the consistency of the current mask assignment
            for i in range(n):
                # Process only if person i is assumed good
                if mask & (1 << i):
                    # Verify each statement person i made
                    for j in range(n):
                        if statements[i][j] == 2:
                            # No statement, so ignore
                            continue
                        if statements[i][j] == 1:
                            # Person i says person j is good, so person j must be in the mask.
                            if not (mask & (1 << j)):
                                valid = False
                                break
                        if statements[i][j] == 0:
                            # Person i says person j is bad, so person j must not be in the mask.
                            if mask & (1 << j):
                                valid = False
                                break
                    if not valid:
                        break
            # If current mask is valid, update max count of good people.
            if valid:
                max_good = max(max_good, bin(mask).count("1"))
        return max_good

# Example usage:
# sol = Solution()
# print(sol.maximumGood([[2,1,2],[1,2,2],[2,0,2]]))
← Back to All Questions