New Year Chaos - HackerRank algorithmic problem - clarifying comments

Hi, guys, I want to discuss an algorithmic problem that's probably easy for most of you, but initially, I found it hard to solve.

The name of the problem is New Year Chaos. It's one of the problems in HackerRank's Solving Interview prep kit.

Here is a link to the problem in HackerRank:

https://www.hackerrank.com/challenges/new-year-chaos

Problem description :

(

Credits to HackerRank

)


Initially, I tried to solve it independently but failed miserably.

Then I found this video with kind of good explanation:

Credits to: @Aditya Pandey for the solution that I used.

https://www.youtube.com/watch?v=RGv_K72p86M


However I still missed some ideas that the solver (Aditya) had in his mind, so I added some additional comments to his solution when I fully understood the way it works :



    /*
     * Complete the 'minimumBribes' function below.
     *
     * The function accepts INTEGER_ARRAY q as parameter.
     */

    /* If we take an input array of numbers:
              Integer[] arr = {2, 1, 5, 3, 4};
            minimumBribes(Arrays.asList(arr));

    Then the comments in this method apply to the above input array.
    */
    private static void minimumBribes(List<Integer> q) {

        int bribesCounter = 0;
        boolean flag = false;

        for(int i = q.size(); i>=1; i--){

            if(q.get(i-1) != i) { //is the last element different than i (5)

                if((i-2)>=0 && q.get(i-2)==i){
                    //we have single bribe occurring

                    /*this will handle the first two elements
                    at the second iteration of the base for loop.*/

                    //swap the values when we have single bribe
                    int swap1 = q.get(i-1); //latest unordered element that is not in the correct position
                    int swap2 = q.get(i-2); //the element next to the latest element also not in the correct position.
                    q.set(i-1, swap2);
                    q.set(i-2, swap1);

                    bribesCounter++;
                } else if ((i-3) >= 0 && q.get(i-3) == i){
                    /*first iteration of the base for loop will first
                     fix the last three numbers in the array: which are 5 ,3 and 2
                    */

                    //double bribe

                    //i-3 is equal to i and i-2 is not
                    //e.g. 2 1 | 5 (i-3)  3 (i-2) 4 (i-1)

                    //swap operations
                    int swap1 = q.get(i-1); //4
                    int swap2 = q.get(i-2); //3
                    int swap3 = q.get(i-3); //5

                    q.set(i-1, swap3); // 5
                    q.set(i-2, swap1); // 4
                    q.set(i-3, swap2); // 3

                    bribesCounter+=2;

                } else {
                    //more than 2 consecutive bribes
                    flag = true;
                    break;
                }
            }
        }

        System.out.println(flag ? "Too chaotic" : bribesCounter);

    }

    public static void main(String[] args) throws IOException {
        Integer[] arr = {2, 1, 5, 3, 4};
        minimumBribes(Arrays.asList(arr));

        Integer[] arr2 = {2, 5, 1, 3, 4};
        minimumBribes(Arrays.asList(arr2));
    }
    
    /*output :
     ==========  
     3
     Too chaotic
     ===========
     */
            


要查看或添加评论,请登录

Yovo Manolov的更多文章

社区洞察

其他会员也浏览了