New Year Chaos HackerRank Solution

New Year Chaos HackerRank Solution

In this New Year Chaos HackerRank solution, It is New Year’s Day and people are in line for the Wonderland rollercoaster ride. Each person wears a sticker indicating their initial position in the queue from  to . Any person can bribe the person directly in front of them to swap positions, but they still wear their original sticker. One person can bribe at most two others.

Determine the minimum number of bribes that took place to get to a given queue order. Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

Example

If person  bribes person , the queue will look like this: . Only  bribe is required. Print 1.

Person  had to bribe  people to get to the current position. Print Too chaotic.

Function Description

Complete the function minimumBribes in the editor below.

minimumBribes has the following parameter(s):

  • int q[n]: the positions of the people after all bribes

Returns

  • No value is returned. Print the minimum number of bribes necessary or Too chaotic if someone has bribed more than  people.

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

Subtasks

For  score 
For  score 

Sample Input

STDIN       Function
-----       --------
2           t = 2
5           n = 5
2 1 5 3 4   q = [2, 1, 5, 3, 4]
5           n = 5
2 5 1 3 4   q = [2, 5, 1, 3, 4]

Sample Output

3
Too chaotic

Explanation

Test Case 1

The initial state:

After person  moves one position ahead by bribing person :

Now person  moves another position ahead by bribing person :

And person  moves one position ahead by bribing person :

So the final state is  after three bribing operations.

Test Case 2

No person can bribe more than two people, yet it appears person  has done so. It is not possible to achieve the input state.

New Year Chaos HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

def minimumBribes(q):
    bribes = 0
    for i in range(len(q), 0, -1):
        if q[i-1] != i:
            if q[i-2] == i:
                q[i-2], q[i-1] = q[i-1], q[i-2]
                bribes += 1                
            elif q[i-3] == i:
                q[i-3], q[i-2], q[i-1] = q[i-2], q[i-1], q[i-3]  
                bribes += 2
            else:            
                print('Too chaotic')
                return            
    print(bribes)

Problem Solution in Java

 public static void minimumBribes(List<Integer> q) {
        int[] persons = {1, 2, 3};
        int brides = 0;
        for(int i = 0; i < q.size(); i++){
            if(q.get(i) == persons[0]){
                persons[0] = persons[1];
                persons[1] = persons[2];
                persons[2]++;
            }else if(q.get(i) == persons[1]){
                persons[1] = persons[2];
                persons[2]++;
                brides++;
            }else if(q.get(i) == persons[2]){
                persons[2]++;
                brides += 2;
            }else{
                System.out.println("Too chaotic");
                return;
            }
        }
        System.out.println(brides);
    }

Problem Solution in JavaScript

function minimumBribes(q: number[]): void {
  // Write your code here
  let total = 0
  for(let i = 0; i < q.length; i++){
      const original_pos = q[i] - 1
      const diff = original_pos - i
      if(diff > 2) return console.log("Too chaotic")
      // we need to bribe from forward person to the person in front of current position
      for(let j = original_pos - 1; j < i; j++){
          if(q[j] - 1 > original_pos) total++
      }
  }
  return console.log(total)
}

Problem Solution in C++

void minimumBribes(vector<int> q) {
    for(int i=0;i<q.size();i++){
        if(q[i]-i-1>2) {
            std::cout<<"Too chaotic"<<std::endl;
            return;
        }
    }
    int count=0;
    int numtoindex[q.size()+1];
    //init
    for(int i= 0;i<q.size();i++) numtoindex[q[i]]=i+1;
   
    for(int i=1;i<q.size()+1;i++){
        if(numtoindex[i]>i){
            for(auto it=std::next(q.begin(),numtoindex[i]-1);it>std::next(q.begin(),i-1);it--){
                std::iter_swap(it,std::prev(it,1));
                numtoindex[*it]++;
                count++;
            }
        }
    }
   
    std::cout<<count<<std::endl;
}
Solve original Problem on HackerRank here. Checkout more HackerRank Problems