02/5/21

HackerRank ‘Majority’ Solution

Short Problem Definition:

Neo has to save the world one last time. One of the battles has cost Neo his eyes. He has to fight the battle with the Deus ex machina.

In front of Neo is a set of N balls, each ball is color coded 0/1. Deus ex machina wants Neo to figure out which ball’s color is the majority ( appears more than > N/2 ). If his choice of ball is correct, Deus ex machina will reach a truce and let humans live and if Neo fails to identify the ball with the majority, the entire human race would be put back into matrix.

Neo being blind won’t be able to see the balls let alone figure out the ball with the majority. He seeks the Oracle’s help. Neo picks any two balls from the set and asks Oracle if they are of the same color or not. If they are the same color, the Oracle answers YES and if they are not, Oracle answers NO. We will call b0/1 as ball b with color 0/1 respectively. Majority exists in this set, i.e.,

Link

Majority

Complexity:

time complexity is O(N^2)

space complexity is O(1)

Requested By:

Soha

Execution:

Comments in code. The solution only achieves 13/23 points. I am open to suggestions in the comments!

You can further reduce the number of queries/asks by doing a binary search. Lets imagine that 2 3 YES and 4 5 YES. In the algorithm below, I compare both to 0. It should be possible to compare them to each other. If the 2 4 is NO, we no longer care. If it is YES, it can be compared to the next bucket.

Solution:
#!/usr/bin/py

def nextQuestion(n, plurality, lies, color, exact_lies, query):
    # the logic assumes that if two elements are not the same, they can be ignored from the majority computation
    # lets say that 3,4 and not-equal, and there are only 2 options, we can safely ignore them (hence not degrade to O(N^2))
    # the algorithm executes in 3 stages
    
    # Stage 1)
    # establish whether distinct pairs are same or equal, we in the future, we can ignore all not-equal pairs
    for i in xrange(0, n, 2):
        if not i + 1 in query[i]:
            return str(i), str(i + 1)

    # Stage 2)
    # This stage collapses all equal pairs into the map for element 0
    # example: 
    # 2 3 YES; 0 2 NO -> 0 2 NO; 0 3 NO
    # 2 3 YES; 0 2 YES -> 0 2 YES; 0 3 YES
    for a, v in query.items():
        if a == 0:
            continue
        for b, val in v.items():
            if b == 0:
                continue
            if val == 0:
                # we ignore non-equal pairs, they do not affect the majority
                continue
            if a in query[0]:
                query[0][b] = query[0][a]
                continue
            # Ask a question for all equal pairs and compare them to 0
            # they can either be part of the 0 majority or not
            return str(0), str(a)

    # Stage 3)
    # All relevant pairs are collapsed into 0
    # Pick the bigger group and establish that it is the majority
    group_0 = [0]
    group_not_0 = []
    for k, v in query[0].items():
        if v == 1:
            group_0.append(k)
        else:
            group_not_0.append(k)

    if len(group_0) > len(group_not_0):
        return [str(0)]
    else:
        return [str(group_not_0[0])]


if __name__ == '__main__':
    vals = [int(i) for i in raw_input().strip().split()]
    query_size = input()
    query = {}
    for i in range(vals[0]):
        query[i] = {}

    for i in range(query_size):
        temp = [j for j in raw_input().strip().split()]
        if temp[2] == "YES":
            query[int(temp[0])][int(temp[1])] = 1
            query[int(temp[1])][int(temp[0])] = 1
        else:
            query[int(temp[0])][int(temp[1])] = 0
            query[int(temp[1])][int(temp[0])] = 0

    print
    " ".join(nextQuestion(vals[0], vals[1], vals[2], vals[3], vals[4], query))


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwitterredditpinterestlinkedin