New Year Chaos — HackerRank solution in C++

So this is an interesting problem I found recently in the interview preparations track of HackerRank.

I’d urge you to see the question in HackerRank and try solving it on your own before reading up the solution and the logic behind it.

Here, we have some number of people standing in a line, and each of them is wearing a jacket denoting their initial position in the line. So if we had like 5 people, their initial positions will be [1 2 3 4 5 6 7 8 ].

A guy standing at a particular position can bribe the person standing in front of him and then swap positions with him, but they’ll still be wearing the same jacket which showed their initial position in the line. One can bribe at most 2 people in the line.

Suppose after bribing, we have the line like this [1 2 5 3 7 8 6 4], we have to find the minimum number of bribes that took place to get our line to the current state.

If a person has bribed more than 2 people, then we have to print “too chaotic”

Solution

void minimumBribes(vector<int> v) {
    int n_swaps=0;
    int flag=0;
    for(int i=v.size()-1;i>=0;i--){
        int key = v[i];
        int j=i+1;
        int max_limit=0;
        while((j<v.size()) && (key>v[j])){
            if(max_limit<2){
                v[j-1]= v[j];
                j++;
                max_limit++;
                n_swaps++;
            }
            else{
                flag++;
                break;
            }
        }
        if(!flag)
            v[j-1]= key;
        else{
            break;
        }
    }
   if(!flag)  cout << n_swaps <<"\n";
   else       cout << "Too chaotic" <<"\n";
}

Explanation :

As you can see, since people were standing in a line initially and only some people were engaged in bribing, we understand that at least some part of the final line is also sorted.

We have learned about the insertion sort algorithm which particularly deals with these kinds of problems. So modifying the insertion sort algorithm to reverse the bribing is the idea that we are using in the solution above.

Here, the loop starts at the end of the array, and tries to maintain a sorted array at the end position. Keeping the sum of the number of positions we have to move to insert a new element to this sorted part, gives the number of bribes done. Also max_limit of 2 is added, so that when we are adding an element, if we are moving more than 2 steps to add it to the sorted part, we know that our person has bribed more than two people which makes our queue “too chaotic” as said in the question.

I hope you all are clear with the solution and if you have any suggestions, feel free to comment.