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:
Problem description :
(
)
领英推荐
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.
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
===========
*/