In this post, we will solve HackerRank New Year Chaos Problem 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 1 to n. 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
q= [1, 2, 3, 5, 4, 6, 7, 8]
If person 5 bribes person 4, the queue will look like this: 1, 2, 3, 5, 4, 6, 7, 8. Only 1 bribe is
required. Print 1.
q = [4, 1, 2, 3]
Person 4 had to bribe 3 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 2 peop
Input Format
The first line contains an integer t, the number of test cases.
Each of the next t pairs of lines are as follows:
– The first line contains an integer t, the number of people in the queue
– The second line has n space-separated integers describing the final state of the queue.
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
New Year Chaos C Solution
#include <stdio.h>
#include <malloc.h>
typedef struct {
int v;
char s;
} CH;
int sort(CH *a, int n)
{
int i, j, s;
int c = 0;
CH t;
for (i = 0; i < n; i++) {
s = 0;
for (j = 0; j < (n - 1); j++) {
if (a[j + 1].v < a[j].v) {
if (a[j].s >= 2)
return -1;
a[j].s++;
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
c++;
s = 1;
}
}
if (s == 0)
break;
}
return c;
}
int main()
{
int t, n, i, c;
CH *ch;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
ch = (CH *)calloc(n, sizeof(CH));
for (i = 0; i < n; ++i)
scanf("%d", &ch[i].v);
c = sort(ch, n);
if (c >= 0)
printf("%d\n", c);
else
printf("Too chaotic\n");
free(ch);
}
return 0;
}New Year Chaos C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
bool ok = true;
int ans = 0;
for (int i = n-1; i >= 0; --i) {
if (arr[i] == i+1) continue;
else if (arr[i-1] == i+1) {
swap(arr[i], arr[i-1]);
ans++;
} else if (arr[i-2] == i+1) {
swap(arr[i-2], arr[i-1]);
swap(arr[i-1], arr[i]);
ans += 2;
} else {
ok = false;
break;
}
}
if (ok) {
cout << ans << endl;
} else {
cout << "Too chaotic" << endl;
}
}
return 0;
}New Year Chaos C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int T = Convert.ToInt32(Console.ReadLine());
for(int a0 = 0; a0 < T; a0++){
int n = Convert.ToInt32(Console.ReadLine());
string[] q_temp = Console.ReadLine().Split(' ');
int[] q = Array.ConvertAll(q_temp,Int32.Parse);
int[] p = new int[n];
int[] c = new int[n];
for(int i=0; i<n; i++) {
p[i] = i+1;
}
bool good = true;
int count = 0;
for(int i=0; good && i<n; i++) {
if(q[i] != p[i]) {
if(q[i] == p[i+1]) {
int k = p[i+1];
p[i+1] = p[i];
p[i] = k;
c[k-1]++;
count++;
if(c[k-1] > 2) good = false;
} else if(q[i] == p[i+2]) {
int k = p[i+2];
p[i+2] = p[i+1];
p[i+1] = p[i];
p[i] = k;
c[k-1] += 2;
count += 2;
if(c[k-1] > 2) good = false;
} else {
good = false;
}
}
}
if(good) Console.WriteLine(count);
else Console.WriteLine("Too chaotic");
}
}
}New Year Chaos Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'minimumBribes' function below.
*
* The function accepts INTEGER_ARRAY q as parameter.
*/
public static void minimumBribes(List<Integer> q) {
int bribeCount = 0;
for(int i = q.size()-1; i>=0; i--){
int index = q.get(i) - (i+1);
if(index > 2){
System.out.println("Too chaotic");
return;
}
else{
int temp = Math.max(0,q.get(i)-2);
for(int k = temp; k < i; k++){
if(q.get(k)>q.get(i)){
bribeCount++;
}
}
}
}
System.out.println(bribeCount);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, t).forEach(tItr -> {
try {
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> q = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
Result.minimumBribes(q);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
}
}New Year Chaos JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function bubbleSort(a)
{
var swapped;
var count = 0;
do {
swapped = false;
for (var i=0; i < a.length-1; i++) {
if(a[i] - (i+1) > 2)
return 'Too chaotic';
if (a[i] > a[i+1]) {
var temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = true;
count++;
}
}
} while (swapped);
return count;
}
function main() {
var T = parseInt(readLine());
for(var a0 = 0; a0 < T; a0++){
var n = parseInt(readLine());
q = readLine().split(' ');
q = q.map(Number);
console.log(bubbleSort(q));
}
}New Year Chaos Python Solution
#!/bin/python3
import sys
T = int(input().strip())
for a0 in range(T):
n = int(input().strip())
q = [int(q_temp) for q_temp in input().strip().split(' ')]
# your code goes here
bribes = [0] + [0]*n
total = 0
end = n-1
bribed = False
for i in range(0, end):
for j in range(0, end):
if q[j] > q[j+1]:
temp = q[j]
bribes[temp] += 1
q[j] = q[j+1]
q[j+1] = temp
bribed = True
if bribed:
bribed = False
else:
break
end -= 1
for b in range(1,n+1):
if bribes[b] > 2:
total = -1
print("Too chaotic")
break
total += bribes[b]
if total >= 0:
print(total)
