HackerRank: ACM ICPC Team

I made a solution to this problem from HackerRank :


You are given a list of N people who are attending ACM-ICPC World
Finals. Each of them are either well versed in a topic or they are
not. Find out the maximum number of topics a 2-person team can know.
And also find out how many teams can know that maximum number of
topics.


Note Suppose a, b, and c are three different people, then (a,b) and
(b,c) are counted as two different teams.


Input Format


The first line contains two integers, N and M, separated by a single
space, where N represents the number of people, and M represents the
number of topics. N lines follow. Each line contains a binary string
of length M. If the ith line's jth character is 1, then the ith person
knows the jth topic; otherwise, he doesn't know the topic.

My code is considered too slow (I think I am allowed 10 seconds, the code below takes more than 20 seconds when N and M are both 500):

```
import random
import itertools
import time

# n number of people
# m number of topics

n = 500
m = 500

"""
binary_string(n) and random_list(n_people, n_topic) just help
to generate test cases, irrelevant otherwise.
"""

def binary_string(n):
my_string = "".join(str(random.randint(0, 1)) for _ in range(n))
return my_string

def random_list(n_people, n_topic):
my_list = [binary_string(n_topic) for _ in range(n_people)]
return my_list

"""
the essential part is item_value(e1, e2)
and find_couples(comb_list)
"""

def item_value(e1, e2):
c = bin(int(e1, 2) | int(e2, 2))
return sum(int(i) for i in c[2:])

def find_couples(comb_list):
max_value = 0
counter = 0

for pair in itertools.combinations(comb_list, 2):
value = item_value(pair[0], pair[1])
if value == max_value:
counter += 1
elif value > max_value:
max_value = value
counter = 1

print(max_value)
print(counter)
return

topic = random_list(n, m

You're spending a lot of time in item_value converting numbers to a binary string back to an int to get the sum. It would be a lot more expedient to just use str.count to get the number of 1s in the string. That saves you a lot of type conversions as well as a call to sum with a generator.

def item_value(e1, e2):
    c = bin(int(e1, 2) | int(e2, 2))
    return c[2:].count('1')

My results from this caused a reduction from 58.9s to 0.91s.

StackExchange Code Review Q#112432, answer score: 10