fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16
https://ideone.com/weHDoP
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!