We will discuss Find the New Year Chaos problem from Hackerrank here.

Problem Statement

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. Initial positions increment by  from  at the front of the line to  at the back.

Rules –

1. Any person in the queue can bribe the person directly in front of them to swap positions.
2. If two people swap positions, they still wear the same sticker denoting their original places in line.
3. One person can bribe at most two others.

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. If anyone has bribed more than two people, the line is too chaotic to compute the answer.

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

• 1 <= t <= 10
• 1 <= n <= 10⁵

In this problem, we need to check if the given array can be rearranged into a sorted array by following the rules.

Solution: New year chaos

As the question only asks about the number of bribes all you need to do is to count the number of people who overtake a person.

Two points to keep in mind while solving this problem:

• A person can bribe the one who is sitting just in front of him. The opposite is not possible.
• A person can bribe at most 2 different persons.

Approach

We are using two loops here.

Outer loop runs backwards and if the difference between current value and current index is greater than 2, then print “Too chaotic” and return. Why we are checking specifically 2, because as per the rule we can bribe as most 2 different persons.

Inner loop runs from, and if value and j^th position is greater than value at i^th position than update the sum.

Code implementation