LC-2151 Hard LeetCode

2151. Maximum Good People Based on Statements

Array Backtracking Bit Manipulation Enumeration

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 51% Topics: Array, Backtracking, Bit Manipulation, Enumeration

Reading material

Arrays & Hashing 12 min Backtracking 14 min Bit Manipulation 10 min

Reference solution (spoiler · python)

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

# brute force, bitmask
class Solution(object):
    def maximumGood(self, statements):
        """
        :type statements: List[List[int]]
        :rtype: int
        """
        def check(mask):
            return all(((mask>>j)&1) == statements[i][j]
                       for i in xrange(len(statements)) if (mask>>i)&1 
                       for j in xrange(len(statements[i])) if statements[i][j] != 2)

        def popcount(x):
            result = 0
            while x:
                x &= x-1
                result += 1
            return result

        result = 0
        for mask in xrange(1<<len(statements)):
            if check(mask):
                result = max(result, popcount(mask))
        return result

Solution from kamyu104/LeetCode-Solutions · MIT