Skip to content

Instantly share code, notes, and snippets.

@oskar-j
Last active August 29, 2015 14:26
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 oskar-j/8ffac703694936f3bd17 to your computer and use it in GitHub Desktop.
Save oskar-j/8ffac703694936f3bd17 to your computer and use it in GitHub Desktop.
Find a point in an array of integers in Java, which divides an array into 2 halfs making best asymetry
public class Asymetry {
public static int solution(int X, int[] A) {
int n = -1;
int right = A.length - 1;
int left = 0;
int rightCounter = 0;
int leftCounter = 0;
if (A[right] != X) rightCounter++;
if (A[left] == X) leftCounter++;
while (left != right) { // takes at most O(n) time
if (leftCounter > rightCounter) {
right--;
if (A[right] != X) rightCounter++;
} else {
left++;
if (A[left] == X) leftCounter++;
}
}
if (right > 0) {
return right == A.length - 1 ?
leftCounter == 0 ? n : right : right;
} else return n;
}
public static void main(String[] args) {
System.out.println(solution(5, new int[]{5, 5, 1, 7, 2, 3, 5}));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment