6
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Use int(input(),2) to convert those binary numbers into its decimal equivalent

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

It's better to use count()

Here is the code:

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

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

for x in range(ppl):
    for y in range(x+1, ppl):
        pairs_list.append(bin(knowledge[x] | knowledge[y]).count('1'))

print(max(pairs_list))
print(pairs_list.count(max(pairs_list)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.