New Year Chaos | HackerRank
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 1 from 1 at the front of the line to ‘n’ 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!
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 2 people.
Test Case 1
INPUT : 2, 1, 5, 3, 4
OUTPUT : 3
Test Case 2
INPUT : 2, 5, 1, 3, 4
OUTPUT: Too chaotic
Explanation
Test case 1
The initial state:
After person 5 moves one position ahead by bribing person 4:
Now person 5 moves another position ahead by bribing person 3 :
And person 1 moves one position ahead by bribing person 1 :
So the final state is 2,1,5,3,4 after three bribing operations.
Image Source: Hackerrank
Test Case 2
No person can bribe more than two people, so it’s not possible to achieve the input state.
Logic
- First create a new queue with no bribe Ex: {1,2, 3, 4,5}
- Get the final queue q[] (after bribe) from the user.
- Start from the first index of final queue array and sequentially search for that element in the new queue ar[].
- If found, check whether the element bribe or not. It is a bribe if the index of ar[] queue is lesser than the index of q[]. Ex: i<j
- Check whether the number of person bribed is two or lesser. If exceed two then print “Too chaotic”.
- If Number of person bribed is two, then reorder three elements.
- If Number of person bribed is one, then reorder two elements.
- Print the total number of bribe at the end.
Program
#include<stdio.h>
void main()
{ /*you can specify any queue and check the output*/
int q[]= {2,1,5,3,4}; //final queue
int q_count=5; //queue count
int ar[q_count];
int i,j,cnt=0,flag=0,temp;
for(i=1;i<=q_count;i++)
{
ar[i-1]=i; //create a new array for initial state
}
for(i=0;i<q_count&&!flag;i++) //loop for final queue
{
for(j=0;j<q_count;j++) //check each element of final queue with every item of intial queue
{
if(q[i]==ar[j])
{
if(i==j) //No bribe (or) element is in same position in q[] and ar[]
break;
else if(j>i) //bribe
{
if((i+2)==j||(i+2)>j) //condition check whether max bribe is 2
{
cnt += (j-i); //count of bribe
if(j-1==i) //bribe only one person (or) moved one position front
{
temp = ar[j]; //Reorder two elements after bribe
ar[j] =ar[i];
ar[i]=temp;
}
else{
/*bribe two person
reorder three elements*/
temp= ar[j];
ar[j]=ar[i+1];
ar[i+1]=ar[i];
ar[i]=temp;
}
break;
}
else/*bribe exceed more than two person*/
{
printf("Too chaotic\n");
flag =1;
break;
}
}
}
}
}
if(!flag)
printf("%d\n",cnt);
}
You might also like…
mycustomwhatsappstickers-android-app
