fork download
  1. import java.util.Arrays;
  2.  
  3. class SplitCoin {
  4. public int split(int[] coins) {
  5. int[] upper = null;
  6. int[] lower = null;
  7. int smallestDifference = 0;
  8.  
  9. Arrays.sort(coins);
  10.  
  11. lower = Arrays.copyOfRange(coins, 0,coins.length-1);
  12. upper = Arrays.copyOfRange(coins, coins.length-1,coins.length); //(after sorting) put the largest element in upper
  13.  
  14. smallestDifference = Math.abs(arraySum(upper) - arraySum(lower));
  15. return findSmallestDifference(lower, upper, arraySum(lower), arraySum(upper), smallestDifference);
  16. }
  17.  
  18. private int findSmallestDifference (int[] lower, int[] upper, int lowerSum, int upperSum, int smallestDifference) {
  19. int[] newUpper = null, newLower = null;
  20. int currentDifference = Math.abs(upperSum-lowerSum);
  21. if (currentDifference < smallestDifference) {
  22. smallestDifference = currentDifference;
  23. }
  24. if (lowerSum < upperSum || lower.length < upper.length || lower[0] > currentDifference
  25. || lower[lower.length-1] > currentDifference
  26. || lower[lower.length-1] < upper[0]/lower.length) {
  27. return smallestDifference;
  28. }
  29. for (int i = lower.length-1; i >= 0 && smallestDifference > 0; i--) {
  30. newUpper = addElement(upper, lower[i]);
  31. newLower = removeElementAt(lower, i);
  32. smallestDifference = findSmallestDifference(newLower, newUpper,
  33. lowerSum - lower[i], upperSum + lower [i], smallestDifference);
  34. }
  35. return smallestDifference;
  36. }
  37.  
  38. private int arraySum (int[] array) {
  39. int result = 0;
  40. for (int current : array){
  41. result += current;
  42. }
  43. return result;
  44. }
  45.  
  46. private int[] addElement (int[] array, int element) {
  47. int[] result = new int[array.length+1];
  48. System.arraycopy(array, 0, result, 0, array.length);
  49. result[array.length] = element;
  50. return result;
  51. }
  52.  
  53. private int[] removeElementAt (int[] array, int index) {
  54. int[] result = new int[array.length-1];
  55. System.arraycopy(array, 0, result, 0, index);
  56. System.arraycopy(array, index+1, result, index, result.length-index);
  57. return result;
  58. }
  59.  
  60. public static void main(String[] args) { //debug
  61. int[] temp = {851,886,91,128,942,395,976,872,337,334};
  62. /*
  63.   int[] temp = {100000,919,445,108,329,566,51,611,69,289,
  64.   479,671,916,185,667,450,988,107,861,668,186,277,
  65.   123,551,352,350,997,189,654,151};
  66. */
  67. /*
  68.   int[] temp = {100000,60000,60000,60000,60000,60000,60000,60000,60000,
  69.   60000,60000,60000,60000,60000,60000,60000,60000,60000,
  70.   60000,60000,60000,60000,60000,60000,60000,60000,60000,
  71.   60000,60000,60000};
  72. */
  73. SplitCoin sc = new SplitCoin();
  74.  
  75. System.out.println(sc.split(temp));
  76. }
  77.  
  78. }
Success #stdin #stdout 0.03s 245632KB
stdin
Standard input is empty
stdout
16