HackerRank New Year Chaos Problem Explained with Solution.

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n= 8 and Person 5 bribes Person 4 , the queue will look like this: 1,2,3,5,4,6,7,8.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

Function Description

Complete the function minimumBribes in the editor below. It must print an integer representing the minimum number of bribes necessary, or Too chaotic if the line configuration is not possible.

minimumBribes has the following parameter(s):

• q: an array of integers

Input Format

The first line contains an integer , the number of test cases.

Each of the next pairs of lines are as follows:
- The first line contains an integer , the number of people in the queue
- The second line has space-separated integers describing the final state of the queue.

Constraints

1≤ t ≤10

1≤ n ≤10⁵

Subtasks

For 60% score 1≤ n ≤10³
For 100% score 1≤ n ≤10⁵

Output Format

Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than people.

Sample Input

2
5
2 1 5 3 4
5
2 5 1 3 4

Sample Output

3
Too chaotic

Link to the Question:

https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Now let’s try to understand the problem:

The Persons in the queue are in positions of the first person to the last person who wants to have a ride. Thus, the bribe only takes place in one direction from the back to the front i.e a person can only bribe someone in a position ahead of him. So, the person in the first position will not bribe the person in the second position but the opposite will happen. Keep this in mind.

So, for example we have 1,2,3,4,5 assume these numbers as the initial positions of persons who need to have a ride. From the sample input, after the bribery schemes we have 2,1,5,3,4. It means Person 2 bribed Persons 1 and Person 5 bribed Person 4 and Person 3. Also, take not the maximum number of bribes is only two per person. Since no one person bribed no more than two persons it satisfies the condition of the maximum bribes and hence we print the number of bribes that occurred. In this case, 3.

From the second sample after the bribery scheme we have 2,5,1,3,4. It means after Person 2 bribed Persons 1, Person 5 bribed Person 4, 3, and 1 respectively. Take note that a person can only bribe the person right in front of him and the maximum number of bribes is 2. Here the sequence can be illustrated as

1. After Person 2 bribery we have [2,1,3,4,5]
2. After Person 5 bribery we have [2,5,1,3,4].

From these observations we can see that Person 5 seems to be greedy and has bribed more than two persons hence causing chaos.

Further, since the bribery scheme is basically a swapping of elements in a sorted list, to know the number of swaps we can reverse engineer the given sample inputs, say to 2,1,5,3,4 to their initial positions of 1,2,3,4,5 by placing a counter to counter each swap until each element reaches their initial positions. From here the comparing sorting algorithm which comes in mind should be Bubble Sort. However, a solution with bubble sort will give a time complexity of O(n²) which is too much time. We should always favor linear timings of O(n) or less. If you don’t know about time complexities I suggest you learn about Big O Time Complexities from Abdul Bari on Youtube.

A naive or brute force solution with Bubble Sort Algorithm will look like this:

Note that int[] q array already contains the sample inputs and is being passed as an argument to the method minimumBribes.

static void minimumBribes(int[] q) {
//define a chaotic situation: Since index starts from 0. make the initial positions as  index + 1. If the element the initial position is greater than two then it's too chaotic.
       for(int i=0;i<q.length;i++){
            if((q[i] - (i+1)) > 2){
                System.out.println("Too chaotic");
                return; 
            }
        }
               
 //After defining a chaotic situation, now we just need to count the number of Swaps utilising the bubble sort algorithm
        int count=0;
        for(int i=q.length-1;i>0;i--){
            for(int j=0;j<q.length;j++){
                if(q[j] > q[j+1]){ 
                    int temp=q[j];
                    q[j]=q[j+1];
                    q[j+1]=temp;
                    count++;
                }
            }
        }
        
        System.out.println(count);
    
    }

Now let’s implement the efficient algorithm with Time Complexity of O(n):

To begin with let indicate if there has been bribery or not. That is if each element is at its original position.

Suppose we have:

index of arrays: 0 1 2 3 4

elements of arrays: 1 2 3 4 5

index + 1 will be 1 2 3 4 5 from this logic we can determine if the elements in the array have been moved or not. With this write the code to determine bribes as follows:

for(int i=q.length-1; i>0;i--){
if(q[i] !=(i+1)){ 
//e.g: if the element at q[3] is not equal to 4, bribery has occurred.
//now we can determine a legitimate bribery from a chaotic bribery.
}
remember array indexes starts from 0.

Let’s determine legitimate bribery:

Determining one-time bribery:

//count is initialized to zero.
if(q[i-1]==(i+1)){
  count ++;
  swap(q,i-1,i);
}
but there are corner cases so the proper condition should take of it.
if(((i-1)>=0)&& q[i-1]==i+1)){
 count = count + 1;
 swap(q,i-1,i);
}

Determining two-time bribery:

else if(((i-2)>=0)&& q[i-2]==(i+1)){
count= count + 2;
//this means that if the element is two positions away from where it is supposed to be then we  increase the count by two.
//you then reverse egine the sample input by swapping adjacent elements
swap(q,i-2,i-1);
swap(q,i-1,i);

}

Now that we have determined the accepted bribery conditions anything apart from this should cause chaos. Therefore, we can simply write this statement as follows:.

else{
System.out.println("Too chaotic");}

Finally, we print out the number of swaps or minimum bribery which we can say is the number of acceptable briberies in by the Persons in the queue.

else{
System.out.println(count);
}

One more thing.

Java does not have an inbuilt swap function so we code our own swap function. Always remember to write clean code and avoid repetition.

static void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}

The time complexity is for this algorithm is O(n). If you have any further confusion. Watch this wonderful explanation on Youtube.