"ACM ICPC Team" challenge

I'm attempting this question on HackerRank, which states the follows:


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.

In my code below, I replaced \$N\$ with ppl and \$M\$ with topics.

ppl, topics = map(int, input().split())
knowledge = []

max_group = 0
max_topic = 0

for x in range(ppl):
    inp = input()
    x = [int(i) for i in inp]
    knowledge.append(x)

for x in range(ppl):
    for y in range(x+1, ppl):
        current_topic = 0

        for z in range(topics):
            if knowledge[x][z] | knowledge[y][z] == 1:
                current_topic += 1

        if current_topic == max_topic:
            max_group += 1
        elif current_topic > max_topic:
            max_topic = current_topic
            max_group = 1

print(max_topic)
print(max_group)

The solution above should return the correct outputs (passed three test cases), but there are simply way too many loops (5, if I am correct). What are some ways that I can reduce the amount of loops and bring the run-time down?

I don't see a better than \$(O(N^2M))\$ (that is, brute force) solution; however an asymptotic constant could be improved significantly.

First, I recommend to represent an individual knowledge as an integer rather than a list. This way computing a team knowledge is a matter of a single bitwise or, and a number of topics covered is the amount of bits set.

To obtain an integer representation of knowledge, recall that int() takes base as a second argument:

for _ in range(ppl):
        knowledge.append(int(input(), 2))

Then analyze a combined team of x, y knowledge as

team_topics = bit_count(knowledge[x] | knowledge[y])

There are many ways to implement bit_count. Here is a good place to start.

Observations not related to performance:

-
Naming is not particularly good. I expect current_topic to be a loop index running through topics, not the count of topics covered by team. Similarly, max_topic is named as if it represents the maximal index in topics table.

-
Dummy loop variable (x in the input loop) is by convention denoted by _. Seeing _ the reader knows it is dummy, and doesn't look for how it might be used in the code.

StackExchange Code Review Q#105863, answer score: 2