Created
November 13, 2015 09:12
-
-
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
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
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