Java | BitMask | check all combinations of good/bad people
There is only up to 15 people, so we can check all combinations (2^15) and verify them against the statements.\nReject any combination that contradicts the stat
There is only up to 15 people, so we can check all combinations (2^15) and verify them against the statements.\nReject any combination that contradicts the statements of good people (bad may lie) and choose one with the max number of good people.\n```\nclass Solution {\n    static int BAD= 0,  GOOD= 1, UNKNOWN= 2;\n\n    public int maximumGood(int[][] statements) {\n        int n= statements.length;\n        int max= 0, combos= 1<<n;\n        int[] roles= new int[n];\n\t\t// iterate through all combinations of good/bad people using bit masks\n        for(int mask=1; mask<combos; mask++){\n            int count= apply(roles, mask);\n            if(possible(statements, roles))\n                max= Math.max(max, count);\n        }\n        return max;\n    }\n    \n\t// convert bitmask to role array, count good people in this mask\n\t// (this part is optional, you can operate on bitmasks directly, but I like it this way to make the checking function\'s code easy)\n    int apply(int[] roles, int mask){\n        int count= 0, n= roles.length;\n        for(int i=0; i<n; i++){\n            count+= roles[i]= mask & GOOD;\n            mask >>= 1;\n        }\n        return count;\n    }\n\n\t// verify the n x n statement matrix against the current combination of roles\n    boolean possible(int[][] statements, int[] roles){\n        int n= statements.length;\n        for(int i=0; i<n; i++){\n            if(roles[i]==BAD) continue;\n            // only check statements of good people\n            for(int j=0; j<n; j++){\n                if(statements[i][j]==UNKNOWN) continue;\n\t\t\t\t// statement of a good person contradicts the assigned role in this combination\n                if(statements[i][j]!=roles[j]) return false; \n            }\n        }\n        return true;\n    }    \n}
[]