What is a better solution than brute force for this?

Question

Given a finite sequence of positive integers between [0-5] lets say [0,3,1,5,2,4,4,4] and a starting sequence [0,0,0,0,0,0,0,0]. We now want to build our given sequence from the starting sequence by performing stepwise operations. In one step, we can either increase all numbers from our starting sequence by 1 or increase just one index from this sequence by 1. Once we would increase a 5 in this case it would become a 0.

What is the most efficient way to find the solution that requires the least steps? This solution should of course also apply to other inputs (length + upper bound). For the starting sequence we can assume it is always 0 for each index.

The brute force approach could look like this.

int upperBound = 5;
int[] endSequence = {0,3,1,5,2,4,4,4};
int currentBestSteps = Integer.MAX_VALUE;
int currentTimesIncreaseAll = 0;

for(int start = 0;start <= upperBound;start++){ //how many times to increase all
  //counter how many steps required total, starting with start amount of steps
  //since we increase all values 'start' times  
  int counterSteps = start; 

  //go through all end values and calc how many steps required  
  for(int end:endSequence){ 
    if(start <= end){
      counterSteps += end-start;
    }else{
      counterSteps += end+upperBound+1-start;
    }
  }

  System.out.println("solution: increase all "+start+
                     " times, total steps: "+counterSteps);

  if(counterSteps < currentBestSteps){
    currentBestSteps = counterSteps;
    currentTimesIncreaseAll = start;
  }
}
System.out.println("best solution: increase all "+currentTimesIncreaseAll+
                   " times, total steps: "+currentBestSteps);

Results:

solution: increase all 0 times, total steps: 23
solution: increase all 1 times, total steps: 22
solution: increase all 2 times, total steps: 21
solution: increase all 3 times, total steps: 20
solution: increase all 4 times, total steps: 19
solution: increase all 5 times, total steps: 30
best solution: increase all 4 times, total steps: 19

Answer 1

I'm going to provide a way to decrement target original array (call it A) to make [0,0,0,0...], either by decrementing everything or decrementing individual items. This of course is the same question, but with the steps in reverse.

First, calculate the cost for decrementing all the elements one-by-one. Call this cost CMAX and the length of the array N. CMAX = sum_for_all_i(A[i])

Then sort the array, and find each position i where i=0 or A[i] > A[i-1].

For each such position it's easy to calculate the cost that would result from decrementing everything until A[i] reaches 0, and then decrementing one-by-one. It's easy, because we know that everything at index < i will wrap around, and everything with index >= i will not. So:

COST(i) = CMAX + A[i] - A[i] * (N-i) + i*(UPPER_BOUND+1-A[i])

The A[i] is the cost of all the global decrements. The - A[i] * (N-i) is the cost reduction for all the high elements that don't wrap around, and the cost i*(UPPER_BOUND+1-A[i]) is the increased cost for all the elements that wrap around from 0 to UPPER_BOUND.

The lowest COST you find (including CMAX) is your answer. Total complexity is O(N log N), dominated by the sort. If the upper bound is guaranteed to be small, then you can use a counting sort for that and get O(N+k)