Last active
November 11, 2019 13:49
-
-
Save jhines2k7/62ee0b3dbd69e4ec740c912b7bebd57e to your computer and use it in GitHub Desktop.
Working on a Hackerrank solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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