So I've been solving this HackerRank problem and I can't really see why my answer isn't working. I've now seen other people's answers and they make sense but it's a completely different approach and I really want to understand why mine doesn't work. It passes two test cases but not the third one. If you all think it's just mathematically or logically off and can explain why that would be awesome. Thanks!
This is the link to the question: https://www.hackerrank.com/challenges/new-year-chaos/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays
This is my code:
public class Solution {
// Complete the minimumBribes function below.
static void minimumBribes(int[] q) {
int numBribes = 0;
boolean chaotic = false;
// loop through this bribed array named q
for (int i=0; i < q.length; i++){
int ogPos = i+1; // original i
int change = q[i]-ogPos;
// CASE 1: too many changes
if ( change > 2){
System.out.println("Too chaotic");
chaotic = true;
break;
}
// CASE 2: changes have been made
if ( change > 0){
numBribes = numBribes + change;
}
// CASE 3: no changes // we do nothing
}
// loop has ended
if ( chaotic == false){
System.out.println(numBribes);
}
}
Your solution is wrong, because a change in position is not equivalent to a bribe. You can have bribes without a change in position and changes in position without a bribe. Start with 1 2 3 4 5:
1 2 3 4 5
# 3 bribes 2
1 3 2 4 5
# 4 bribes 2
1 3 4 2 5
# 3 bribes 1
3 1 4 2 5
# 2 bribes two people
3 2 1 4 5
2 changed 0 positions with 2 bribes, since bribing goes forward a position but being bribed goes back a position. They key thing to notice is that the only time someone can be ahead of a person with a smaller number (also known as an inversion) is if and only if they bribed that person. There's an O(n^2) naive brute force that can be obtained with this, and O(n*log(n)) solution if you use a fenwick tree, and an O(N) solution if you go from the back, check for bribes in the next two positions, and swap people in order to undo the bribe if one is found.