Skip to content

Instantly share code, notes, and snippets.

@jiahaoliuliu
Created November 13, 2015 09:12
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 jiahaoliuliu/06f238db9cd2c5b1137b to your computer and use it in GitHub Desktop.
Save jiahaoliuliu/06f238db9cd2c5b1137b to your computer and use it in GitHub Desktop.
A simple solution to split a list into two and the sum of the elements are similar
package com.jiahaoliuilu.testing.toptal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test1 {
// Testing array
private static int[] array = {5, 5, 1, 7, 2, 3, 5};
public static void main(String[] args) {
System.out.println(solution(5, array));
}
public static int solution(int X, int[] A) {
return findPosition(createMask(X, A), createInverseMask(X, A));
}
/**
* Create a mask of 0s and 1s which matches with the content of the list.
* For n from 0 to A.length() -1
* - If A[n] == X, then result[n] = 1
* - If A[n] != X, then result[n] = 0
* @param X
* The element to check
* @param A
* The list of element to check
* @return
* A list of 0s and 1s which has the same size as A.
*/
public static List<Integer> createMask(int X, int[] A) {
List<Integer> result = new ArrayList<Integer>();
for (int number : A) {
if (number == X) {
result.add(1);
} else {
result.add(0);
}
}
return result;
}
/**
* Create a mask of 0s and 1s which matches with the content of the list.
* For n from 0 to A.length() -1
* - If A[n] == X, then result[n] = 0
* - If A[n] != X, then result[n] = 1
* @param X
* The element to check
* @param A
* The list of element to check
* @return
* A list of 0s and 1s which has the same size as A.
*/
public static List<Integer> createInverseMask(int X, int[] A) {
List<Integer> result = new ArrayList<Integer>();
for (int number : A) {
if (number == X) {
result.add(0);
} else {
result.add(1);
}
}
return result;
}
/**
* Find the position where the sum of the elements of the mask matches with the sum
* of the reverse of the element of the inverseMask
* @param mask
* The mask to be checked.
* @param inverseMask
* The inverse mask to be checked
* @return
* The first position where the elements matches.
* If there is not such element, return -1
*/
public static int findPosition(List<Integer> mask, List<Integer> inverseMask) {
List<Integer> maskSumList = generateSumList(mask);
// Reverse the inverse mask
Collections.reverse(inverseMask);
List<Integer> inverseMaskReverseSumList = generateSumList(inverseMask);
List<Integer> results = new ArrayList<Integer>();
for (int i = 0; i<maskSumList.size(); i++) {
if (maskSumList.get(i) ==
inverseMaskReverseSumList.get(inverseMaskReverseSumList.size() - i - 1)) {
results.add(i);
}
}
// If the results does not exists, returns -1
// Otherwise return the first element of the result
if (results.isEmpty()) {
return -1;
} else {
return results.get(0);
}
}
/**
* Generate a new list of numbers where each element is the sum of the elements of the original
* list till such position
* @param list
* The list to be checked
* @return
* The list of the sum of the elements
*/
public static List<Integer> generateSumList(List<Integer> list) {
List<Integer> result = new ArrayList<Integer>();
int sum = 0;
for (Integer number : list) {
sum += number;
result.add(sum);
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment