New Year Chaos Discussions |

8 months ago+ 0 comments

Python - the key for me was to think about 'how many people to the right have numbers smaller than me' as those people must have been overtaken (bribed). Then it became a matter of doing the check in a fast enough way to handle the test cases...

def minimumBribes(q):
    
    def find_smaller_than(n, sorted_list):
        # fast (enough) as we stop looking once n > n_bigger
        smaller_than = 0
        for number in sorted_list:
            if number < n:
                smaller_than += 1
            else:
                return smaller_than
        return smaller_than

    bribes = 0
    remaining_queue = sorted(q)
    for person in q:
        remaining_queue.remove(person)
        overtaken = find_smaller_than(person, remaining_queue)
        if overtaken > 2:
            print("Too chaotic")
            return
        bribes += overtaken
    print(bribes)

Cookie support is required to access HackerRank