Java :
static int[] cutTheSticks(int[] arr) {
ArrayList<Integer> sticks = new ArrayList<Integer>();
ArrayList<Integer> sticksToCut = new ArrayList<Integer>();
int noOfSticks = arr.length, smallestStickLength = 1000000, stickLength = 0;
sticks.add(noOfSticks);
for(int m = 0; m < noOfSticks; m++){
sticksToCut.add(arr[m]);
}
while(noOfSticks > 0){
smallestStickLength = 1000000;
for(int j = 0; j < sticksToCut.size(); j++){
if(sticksToCut.get(j) < smallestStickLength){
smallestStickLength = sticksToCut.get(j);
}
}
for(int k = 0; k < sticksToCut.size(); k++){
if(sticksToCut.get(k) == smallestStickLength){
sticksToCut.remove(k);
k--;
}else{
stickLength = sticksToCut.get(k) - smallestStickLength;
sticksToCut.set(k, stickLength);
}
}
noOfSticks = sticksToCut.size();
if(noOfSticks != 0){
sticks.add(noOfSticks);
}
}
Integer[] sticksLeft = new Integer[sticks.size()];
sticks.toArray(sticksLeft);
int[] sticksLeftEachRound = new int[sticksLeft.length];
for(int i = 0; i < sticksLeft.length; i++){
sticksLeftEachRound[i] = sticksLeft[i];
}
return sticksLeftEachRound;
}
Explanation:
Warning: Lots of converting from ArrayLists to Arrays and vice versa ahead!
First, convert the ArrayList sticks to store the number of sticks left after each cut-and-throw round. Add the original uncut number of sticks into the sticks arraylist. Convert the arr array into sticksToCut arraylist with a for loop (looping with m).
Next, while the number of sticks left to cut is greater than 0, find the shortest stick length with the for loop j. The for loop k finds each of the sticks which is the same length as the smallest stick, and removes the stick from the sticksToCut arraylist. k- – is used to check the next stick at index k, since the previous stick would be removed if it is the shortest, and would push the entire arraylist forward. Otherwise, cut the length of the shortest stick from each of the longer sticks, and set the stick at index k to be the new cut length.
Check the number of sticks left after each cut and toss round with sticksToCut.size(). If the number of sticks left is 0, don’t add it to the sticks arraylist. Convert sticks arraylist to an Integer array sticksLeft
Next is converting Integer array to int array. Note that these are two different types: Integer in Java is a wrapper class, while int is a primitive class for numbers. The for loop i copies each int sticksLeftEachRound element from sticksLeft Integer array.