Question:
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 from 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 and bribes , the queue will look like this: .
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.
- 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.
Subtasks
For score
For score
For score
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
Solution:
The Solution is a little tricky and has some edge cases.
The thing to keep in mind while solving this problem is that the array will be too chaotic if the difference at value at index i and the (i+1) is more than 2. (just write it on paper and try to dry run it).
Steps:
- check for each position if it contains a value which would have travelled 3 or more places from the right , what I am trying to say is ( arr[index] - (index + 1) <= 2 ) if this is not satisfied means array is too chaotic.
- The failure case is taken care, now we just have to minimize the swaps for that we will use two pointer technique.
- I have a pointer as end and using the value at end I will assign the start.
- Now as the start will increment I will check if the arr[start] > arr[end] means the values are swapped and I will increment the swap counter.
- I will repeat the above process for all values of end from arr.length-1 to 0.
The code is shared below.
static void minimumBribes(int[] arr) {
int bribes=0,swap=0;
int start=0 , end=0 , pos = 0;
int n=arr.length-1;
for(end = n ; end >= 0 ; end--){
start = 0;
bribes = arr[pos]-(pos+1);
if(bribes > 2){
System.out.println("Too chaotic");
return;
}
if(arr[end] - 2 > 0){
start = arr[end] - 2;
}
while(start <= end){
if(arr[start] > arr[end]){
swap++;
}
start++;
}
pos++;
}
System.out.println(swap);
return;
}
The time complexity of the above solution is O(n)
Thanks for reading, hope it helps.
New Year Chaos: Hackerrank Solution.
Reviewed by Jas Arora
on
May 31, 2020
Rating:
No comments:
If you have any doubts please let me know.