Explained optimised bit manipulation || beats 99% Time || beats 100% Space
\n\n\n\n# Intuition\niterate over each possible configuration of good and bad people using bit manipulation.\n\n# Approach\n#### Representing a configuration\nR
\n![image.png](https://assets.leetcode.com/users/images/1e39b967-5654-4e4f-94d0-be2a14dc9c47_1716551346.4571552.png)\n\n\n# Intuition\niterate over each possible configuration of good and bad people using bit manipulation.\n\n# Approach\n#### Representing a configuration\nRepresent a possible configuration of `n` people using `n` bits.\n\n- 1 = good person\n- 0 = bad person\n\nE.g. `1010` = People 1,3 are good. People 2,4 are bad.\n\n##### Naive approach to testing configs\nWe can iterate over all the possible configurations, starting with all people lying, like so:\n```\nfor(int config=0; config<(1<<n); config++){\n    // check if the solution is valid\n}\n```\n\n##### Improved approach to testing configs\nWe 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:\n\nIf `maxGood` is 3, then we need at least 4 truthful bits to find a better solution. For example, if `config`=`00111`, then we can stop because `config` is decreasing.\n\n- initialise config = `111...1111` \n- stop searching when `config < (1<<maxGood)`\n\n\n```\nfor(int config=(1<<n)-1; config >= (1<<maxGood); config--){\n    // check if the solution is valid\n}\n```\n\n#### Check if a solution is valid\nA solution is invalid when some who is assumed to be truthful tells a lie. (Ignore what the liars say.)\n\nTherefore, iterate over all the truthful people in a solution and check what they say matches our proposed solution.\n\n```\nbool configurationWorks = true;\n// iterate over each person in the config\nfor(int j=0; j<n && configurationWorks; j++){\n    if((config>>j)&1){\n        // the current person is telling the truth\n        for(int h=0; h<n; h++){\n            // the accused is not what they are supposed to be\n            // e.g. person j says person h is good when they are bad\n            if(statements[j][h] != 2 && statements[j][h] != ((config>>h)&1)){\n                configurationWorks = false;\n                break;\n            }\n        }\n    }\n}\n```\n\n#### setting the new max score\nThe 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`.\n\n```\nif(configurationWorks){\n    maxGood = max(maxGood, __builtin_popcount(config));\n}\n```\n\n\n# Complexity\n- Time complexity: O(N^2 * 2^N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(sqrt(N))\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maximumGood(vector<vector<int>>& statements) {\n        int n = statements.size();\n        int maxGood = 0;\n        // config has n bits. A 1 represents good, and a 0 represents bad\n        for(int config=(1<<n)-1; config >= (1<<maxGood); config--){\n            bool configurationWorks = true;\n            // iterate over each person in the config\n            for(int j=0; j<n && configurationWorks; j++){\n                if((config>>j)&1){\n                    // the current person is telling the truth\n                    for(int h=0; h<n; h++){\n                        // the accused is not what they are supposed to be\n                        // e.g. person j says person h is good when they are bad\n                        if(statements[j][h] != 2 && statements[j][h] != ((config>>h)&1)){\n                            configurationWorks = false;\n                            break;\n                        }\n                    }\n                }\n            }\n            if(configurationWorks){\n                maxGood = max(maxGood, __builtin_popcount(config));\n            }\n        }\n        return maxGood;\n    }\n};\n\n```
['C++']