HackerRank New Year Chaos Problem Solution

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

HackerRank New Year Chaos Problem Solution

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)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python