acm_icpc_team.py

# source: https://www.hackerrank.com/challenges/acm-icpc-team/problem
# video: https://youtu.be/tfHd30CGAWs

def acmTeam(topic):
    # keep track of teams (hashmap/dict)
    teams = {}
    length = len(topic)
    for i in range(length - 1): # O(n)
        curr_bin_string = topic[i] # first team member
        # Take each bit set and use OR operation to create combined topic knowledge team
        for j in range(i + 1, length): # second team member | # O(n)
            second_bin_string = topic[j]
            combo = int(curr_bin_string, 2) | int(second_bin_string,2) # O(m)
            combo_bin_string = '{:b}'.format(combo)
            # store in hashmap/dict with running count
            if combo_bin_string not in teams:
                teams[combo_bin_string] = 0
            teams[combo_bin_string] += 1

    # get max key length of "1"s and count of teams
    max_length = 0
    for key in teams.keys(): # O(n^2)
        count_of_ones = key.count('1') # O(m)
        max_length = max(max_length, count_of_ones)

    # return max_length AND sum of max key length of "1"s team counts
    team_sums = sum([count for key, count in teams.items() if key.count('1') == max_length]) # O(n^2) * O(n)
    return max_length, team_sums
    # Total Time Complexity = O(n * n * m) + O(n * n * m) + O(n * n * m) + O(n * n)
    # => O(3n^2*m) + O(n^2) => O(3n^2*m) => O(n^2*m)