Algorithms

HackerRank New Year Chaos Challenge

Print the number of bribes, or, if anyone has bribed more than two people, print Too chaotic.

---

The details for the problem detailed in this post can be found at https://www.hackerrank.com/challenges/new-year-chaos/problem

The following solution is written in Javascript.

Problem

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]
  

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 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 & Validation

    1 <= t <= 10
    1 <= n <= 10^5
  

Sample Input 0

   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 0

    3
    Too chaotic
  

Explanation

The first n = 10 letters of the infinite string are abaabaabaa. Because there are 7 a's, we return 7.

Test Case 1

After person 5 moves one position ahead by bribing person 4:

Now person 5 moves another position ahead by bribing person 3:

And person 2 moves one position ahead by bribing person 1:

So the final state is 2,1,5,3,4 after three bribing operations.

Test Case 2

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

First Attempt

We will first add a statement that will simply return n id the string is 'a'.

    if(s == 'a') return n;
    

We then create the substring by creating an array from the string to loop through.

    let array = s.split(''),
        count = 0,
        aCount = 0,
        substring = '';

        while (count < n) {
            if(newString.length == n) break;
            if(count == array.length) count = 0;
            newString += array[count]
            count++;
        }

Finaly we return the frequency of a in the substring

    return newString.split('a').length-1;;

The full function is as below:

    function repeatedString(s, n) {

        if(s == 'a') return n;

        let array = s.split(''),
            count = 0,
            aCount = 0,
            newString = '';

        while (count < n) {
            if(newString.length == n) break;
            if(count == array.length) count = 0;
            newString += array[count]
            count++;
        }

        return newString.split('a').length-1;;
    }

Although this function worked it failed on a number of test cases due to the Time limit exceeding. The method above is far from optimized and is more of a brute force attempt.

Second Attempt

For my second attempt I decided that instead of using loops I could calculate the frequency of 'a' in s and then calculate how many times the string can be repeated in n.

    let aInString = (s.split('a').length - 1),
        frequency = Math.floor(n/(s.length)) * aInString;
    

One thing to consider here though is the fact that there could be a number of characters remaining after we divide n by the length of s. We can work out how many characters, if any, are left with the modular operator:

    remStringLength = n % s.length;
    

We can now use the slice method to get the actual string remaining and use the split method we've already used to return the frequency of 'a' if there are any in the remaining string and add it to the frequency:

    frequency += (s.slice(0, remStringLength).split('a').length - 1);
    

Final Full Function

    function repeatedString(s, n) {

            if(s == 'a') return n;

            let aInString = (s.split('a').length - 1),
                frequency = Math.floor(n/(s.length)) * aInString,
                remStringLength = n % s.length;

            frequency += (s.slice(0, remStringLength).split('a').length - 1);

            return frequency;
        }