Minimum sum such that one of every three consecutive elements is taken

Question

Given an array of n non-negative integers (arr[]), we have to find the minimum sum of elements so that at least one element out of every 3 consecutive elements is picked.

Input : arr[] = {1, 2, 3}
Output : 1

Input : arr[] = {1, 2, 3, 6, 7, 1}
Output : 4
We pick 3 and 1  (3 + 1 = 4)
Note that there are following subarrays
of three consecutive elements
{1, 2, 3}, {2, 3, 6}, {3, 6, 7} and {6, 7, 1}
We have picked one element from every subarray.

Input : arr[] = {1, 2, 3, 6, 7, 1, 8, 6, 2,
                 7, 7, 1}
Output : 7
The result is obtained as sum of 3 + 1 + 2 + 1

The recursive equation for this is given as:

sum[i]= arr[i] + min(sum[i-1],sum[i-2],sum[i-3])
where the base condition is: 
if i==3, then sum(3)= arr[3] + min(sum(0),sum(1),sum(2)) where 
    sum(0)=arr[0]
    sum(1)=arr[1]
    sum(2)=arr[2]
result=min(sum(n-1), sum(n-2), sum(n-3))

Kindly explain the intuition behind the recursive equation formed. Why is it true that addition of the current i^th array element and the min of the results from the last three recursion calls gives us the correct answer for the array of size i?

Answer 1

base on my conversation with @trincot above. I was a bit confused about why there is a function sum() and list sum[]. I did a little search and I think it is because the solution involves using Dynamic Programming to generate a list sum and use it to store the answer as sum[i] if we are using the first i item of the input array.

If you read trincot's answer and got confused and wonder how the code looks like it looks like below (in Java):

import java.lang.Math;
import java.util.Arrays;


public class MinSumThreeConsec{

    public static int minSumThreeConsec(int[] arr){
        int n = arr.length;

        if(n == 0){
            return 0;
        }

        //if the length of the array lenght is 3 or less
        if(n <= 3){ 
            Arrays.sort(arr);
            return arr[0];  
        }

        //if array size is larger than 3 than we need to use DP to pupulate the list sum
        int[] sum = new int[n];

        //fill out the base cases
        sum[0] = arr[0];
        sum[1] = arr[1];
        sum[2] = arr[2];


        for(int i = 3; i<n; i++){
            sum[i] =  arr[i] + min(sum[i-1], sum[i-2], sum[i-3]); //include value at index i in arr. and the mimum value from sum[i-1], sum[i-2], sum[i-3]
        }


        return min(sum[n-1], sum[n-2], sum[n-3]); //refer to trincot's answer above
    }

    public static int min(final int a, final int b, final int c){
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String[] args){

        int[] arr = {};
        System.out.print(minSumThreeConsec(arr)); //empty case print 0

        int[] arr1 = {3,2,1};
        System.out.print(minSumThreeConsec(arr1)); //print 1

        int[] arr2 = {1, 2, 3, 6, 7, 1};
        System.out.print(minSumThreeConsec(arr2)); //print 4

        int[] arr3 = {1, 2, 3, 6, 7, 1, 8, 6, 2, 7, 7, 1}; //print 7
        System.out.print(minSumThreeConsec(arr3));

        int[] arr4 = {1, 2, 3, 6, 7, 1, -8, 6, 2, 7, 7, 1}; //print -1
        System.out.print(minSumThreeConsec(arr4));
    }

}

I think this even works with negative numbers in the list.

Answer 2

The recursive formula is indeed correct, but only if it is extended with the following:

output = min(sum(n-1), sum(n-2), sum(n-3))

... where n is the size of arr. In case n < 3, then the output is the minimum of all arr values of course.

The recursive formula fulfils the requirement "at least one element out of every 3 consecutive elements is picked", which is the same as saying that the index distance between two neighboring picks (or the end of the array) is at the most 3:

• For i >= 3, sum(i) will include the value at i, and at least one of the values at i-1, i-2 or i-3, because the sum definition for each of those includes the value at that index also. Obviously the index difference will be at most i - (i-3), i.e. 3.

• For i < 3, it is true since there are fewer than 3 values preceding them.

The recursive formula (including the necessary formula for the final output), also fulfils the requirement that "the minimum sum of elements" should be output. This is because the optimal solution must include the value at index n-1, n-2 or n-3, otherwise the other condition is not met.

• As sum(i) minimises the sum when i must be included, the minimum among sum(n-1), sum(n-2), sum(n-3) will thus find the optimal solution.