Skip to content

Instantly share code, notes, and snippets.

@jhines2k7
Last active November 11, 2019 13:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jhines2k7/62ee0b3dbd69e4ec740c912b7bebd57e to your computer and use it in GitHub Desktop.
Save jhines2k7/62ee0b3dbd69e4ec740c912b7bebd57e to your computer and use it in GitHub Desktop.
Working on a Hackerrank solution
// int[] q = new int[]{1, 2, 5, 3, 7, 8, 6, 4}; {1, 2, 3, 4, 5, 6, 7, 8}
int[] q = new int[]{2, 1, 5, 3, 4}; //-> 3
// int[] q = new int[]{2, 5, 1, 3, 4}; //-> too chaotic
int[] r = new int[q.length];
boolean inFinalPos = false;
boolean tooChaotic = false;
int numBribes;
int totalBribes = 0;
int finalPos;
HashMap<Integer, Integer> currentPosMap = new HashMap<>();
for(int i = 0; i < q.length; i++) {
r[i] = i + 1;
currentPosMap.put(i + 1, i);
}
for(int i = 0; i < q.length; i++) {
numBribes = 0;
if(q[i] != r[i]) {
// find the current pos of the out of place element
int idx = currentPosMap.get(q[i]);
while(!inFinalPos || !tooChaotic) {
// perform swap operations
int temp = r[idx];
r[idx] = r[idx - 1];
r[idx - 1] = temp;
currentPosMap.put(q[i], idx - 1);
currentPosMap.put(r[idx + 1], idx);
numBribes++;
if(numBribes > 2) {
tooChaotic = true;
}
if(i < idx - 1) {
inFinalPos = true;
}
}
totalBribes += numBribes;
}
if(tooChaotic) {
break;
}
}
if(tooChaotic) {
System.out.println("Too chaotic");
} else {
System.out.println(totalBribes);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment