Explained Ruby 100% performant brute force & backtracked solution O(2^n*n^2)
Intuition & Approach\n### Tip: Since the size of n(15) is small, consider brute force solutions\n \n1. Generate all possible combinations that the persons can h
# Intuition & Approach\n### Tip: Since the size of n(15) is small, consider brute force solutions\n \n1. Generate all possible combinations that the persons can have i.e good, bad, etc (user Ruby\'s inbuilt repeated_permutation method)\n\n2. Assuming that each combination above is true, loop through the statements. We can use the current combination to ensure we are only listening to truthful people, they are the only source of real info. \n\n3. If the truthful person says: \na. That a person we know to be good in our current combination is a bad person. \nb. Or a person we know to be bad in our current combination is a good person. \n##### That combination is invalid and we must throw it out. \n\n4. Loop through all 2^n combinations and save those that are valid. \n\nReturn the valid combination that has the max sum \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n\n# Complexity - O(2^n*n^2)\n- Time complexity: \nLooping through all combinations takes O(2^n)\nFor each combination we loop through all the statements O(n)\nFor each statement we have to loop it to find the comment O(n) \nHence O(2^n*n*n) Tc = O(2^n*n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe use extra space to the possible outcomes\nwhere arr_size = n, possible_outcomes = 2^n \nvalid outcomes can be at most be 2^n \n2^n + 2^n \n\n# Code\n```\ndef maximum_good(statements)  \n    n = statements.size\n    possible_outcomes = [0, 1].repeated_permutation(n).to_a\n\n    valid = []\n    \n    possible_outcomes.each do |truth|\n       valid << truth if  validate_claim(statements, truth) \n    end\n\n    valid.map{|val| val.sum }.max\n\n\nend\n\ndef validate_claim(statements, truthful)\n        #invalid if GP says GP is BP\n        #invalid if GP says BP is GP\n        #we can only trust people in current outcome\n        statements.each_with_index do |comments, stated_by|\n            next unless truthful[stated_by] == 1\n            #trust only good people\n                comments.each_with_index do |comment, stated_for|\n                    next if comment == 2\n                    \n                    gp_is_bp = comment == 0 && truthful[stated_for] == 1\n                    bp_is_gp = comment ==1 && truthful[stated_for] == 0\n\n                    if gp_is_bp || bp_is_gp\n                        return false\n                    end\n                end\n        end\n\n        return true \n\nend\n```
['Ruby']