Find minimum sum such that one of every three consecutive elements is taken
Given an array of n non-negative numbers, the task is to find the minimum sum of elements (picked from the array) such that at least one element is picked out of every 3 consecutive elements in the array.
Examples :
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
Let sum(i) be the minimum possible sum when arr[i] is part of a solution sum (not necessarily result) and is last picked element. Then our result is minimum of sum(n-1), sum(n-2) and sum(n-3) [We must pick at least one of the last three elements].
We can recursively compute sum(i) as sum of arr[i] and minimum(sum(i-1), sum(i-2), sum(i-3)). Since there are overlapping subproblems in recursive structure of problem, we can use Dynamic Programming to solve this problem.
Below is the implementation of above idea.
C++
// A Dynamic Programming based C++ program to find minimum // possible sum of elements of array such that an element // out of every three consecutive is picked. #include <iostream> using namespace std; // A utility function to find minimum of 3 elements int minimum( int a, int b, int c) { return min(min(a, b), c); } // Returns minimum possible sum of elements such that an // element out of every three consecutive elements is // picked. int findMinSum( int arr[], int n) { // Create a DP table to store results of subproblems. // sum[i] is going to store minimum possible sum when // arr[i] is part of the solution. int sum[n]; // When there are less than or equal to 3 elements sum[0] = arr[0]; sum[1] = arr[1]; sum[2] = arr[2]; // Iterate through all other elements for ( int i = 3; i < n; i++) sum[i] = arr[i] + minimum(sum[i - 3], sum[i - 2], sum[i - 1]); return minimum(sum[n - 1], sum[n - 2], sum[n - 3]); } // Driver code int main() { int arr[] = { 1, 2, 3, 20, 2, 10, 1 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Min Sum is %d" , findMinSum(arr, n)); return 0; } |
C
// A Dynamic Programming based C++ program to find minimum // possible sum of elements of array such that an element // out of every three consecutive is picked. #include <stdio.h> // Find minimum between two numbers. int min( int num1, int num2) { return (num1 > num2) ? num2 : num1; } // A utility function to find minimum of 3 elements int minimum( int a, int b, int c) { return min(min(a, b), c); } // Returns minimum possible sum of elements such that an // element out of every three consecutive elements is // picked. int findMinSum( int arr[], int n) { // Create a DP table to store results of subproblems. // sum[i] is going to store minimum possible sum when // arr[i] is part of the solution. int sum[n]; // When there are less than or equal to 3 elements sum[0] = arr[0]; sum[1] = arr[1]; sum[2] = arr[2]; // Iterate through all other elements for ( int i = 3; i < n; i++) sum[i] = arr[i] + minimum(sum[i - 3], sum[i - 2], sum[i - 1]); return minimum(sum[n - 1], sum[n - 2], sum[n - 3]); } // Driver code int main() { int arr[] = { 1, 2, 3, 20, 2, 10, 1 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Min Sum is %d" , findMinSum(arr, n)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// A Dynamic Programming based java program to // find minimum possible sum of elements of array // such that an element out of every three // consecutive is picked. import java.io.*; class GFG { // A utility function to find minimum of // 3 elements static int minimum( int a, int b, int c) { return Math. min(Math.min(a, b), c); } // Returns minimum possible sum of elements such // that an element out of every three consecutive // elements is picked. static int findMinSum( int arr[], int n) { // Create a DP table to store results of // subproblems. sum[i] is going to store // minimum possible sum when arr[i] is // part of the solution. int sum[] = new int [n]; // When there are less than or equal to // 3 elements sum[ 0 ] = arr[ 0 ]; sum[ 1 ] = arr[ 1 ]; sum[ 2 ] = arr[ 2 ]; // Iterate through all other elements for ( int i = 3 ; i < n; i++) sum[i] = arr[i] + minimum(sum[i - 3 ], sum[i - 2 ], sum[i - 1 ]); return minimum(sum[n - 1 ], sum[n - 2 ], sum[n - 3 ]); } // Driver code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 20 , 2 , 10 , 1 }; int n = arr.length; System.out.println( "Min Sum is " + findMinSum(arr, n)); } } // This code is contributed by vt_m |
Python3
# A Dynamic Programming based python 3 program to # find minimum possible sum of elements of array # such that an element out of every three # consecutive is picked. # A utility function to find minimum of # 3 elements def minimum(a, b, c): return min ( min (a, b), c); # Returns minimum possible sum of elements such # that an element out of every three consecutive # elements is picked. def findMinSum(arr,n): # Create a DP table to store results of # subproblems. sum[i] is going to store # minimum possible sum when arr[i] is # part of the solution. sum = [] # When there are less than or equal to # 3 elements sum .append(arr[ 0 ]) sum .append(arr[ 1 ]) sum .append(arr[ 2 ]) # Iterate through all other elements for i in range ( 3 , n): sum .append( arr[i] + minimum( sum [i - 3 ], sum [i - 2 ], sum [i - 1 ])) return minimum( sum [n - 1 ], sum [n - 2 ], sum [n - 3 ]) # Driver code arr = [ 1 , 2 , 3 , 20 , 2 , 10 , 1 ] n = len (arr) print ( "Min Sum is " ,findMinSum(arr, n)) # This code is contributed by Sam007 |
C#
// A Dynamic Programming based C# program to // find minimum possible sum of elements of array // such that an element out of every three // consecutive is picked. using System; class GFG { // A utility function to find minimum of // 3 elements static int minimum( int a, int b, int c) { return Math. Min(Math.Min(a, b), c); } // Returns minimum possible sum of elements such // that an element out of every three consecutive // elements is picked. static int findMinSum( int []arr, int n) { // Create a DP table to store results of // subproblems. sum[i] is going to store // minimum possible sum when arr[i] is // part of the solution. int []sum = new int [n]; // When there are less than or equal to // 3 elements sum[0] = arr[0]; sum[1] = arr[1]; sum[2] = arr[2]; // Iterate through all other elements for ( int i = 3; i < n; i++) sum[i] = arr[i] + minimum(sum[i - 3], sum[i - 2], sum[i - 1]); return minimum(sum[n - 1], sum[n - 2], sum[n - 3]); } // Driver code public static void Main () { int []arr = {1, 2, 3, 20, 2, 10, 1}; int n = arr.Length; Console.WriteLine( "Min Sum is " + findMinSum(arr, n)); } } //This code is contributed by Sam007 |
PHP
<?php // A Dynamic Programming based // PHP program to find minimum // possible sum of elements of // array such that an element // out of every three consecutive // is picked. // function to find minimum of // 3 elements function minimum( $a , $b , $c ) { return min(min( $a , $b ), $c ); } // Returns minimum possible sum // of elements such that an // element out of every three // consecutive elements is picked. function findMinSum( $arr , $n ) { // Create a DP table to store results of // subproblems. sum[i] is going to store // minimum possible sum when arr[i] is // part of the solution. $sum [ $n ] = 0; // When there are less // than or equal to // 3 elements $sum [0] = $arr [0]; $sum [1] = $arr [1]; $sum [2] = $arr [2]; // Iterate through all other elements for ( $i = 3; $i < $n ; $i ++) $sum [ $i ] = $arr [ $i ] + minimum( $sum [ $i - 3], $sum [ $i - 2], $sum [ $i - 1]); return minimum( $sum [ $n - 1], $sum [ $n - 2], $sum [ $n - 3]); } // Driver code $arr = array (1, 2, 3, 20, 2, 10, 1); $n = sizeof( $arr ); echo "Min Sum is " , findMinSum( $arr , $n ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // A Dynamic Programming based Javascript program to // find minimum possible sum of elements of array // such that an element out of every three // consecutive is picked. // A utility function to find minimum of // 3 elements function minimum(a, b, c) { return Math.min(Math.min(a, b), c); } // Returns minimum possible sum of elements such // that an element out of every three consecutive // elements is picked. function findMinSum(arr, n) { // Create a DP table to store results of // subproblems. sum[i] is going to store // minimum possible sum when arr[i] is // part of the solution. var sum= Array(n).fill(0); // When there are less than or equal to // 3 elements sum[0] = arr[0]; sum[1] = arr[1]; sum[2] = arr[2]; // Iterate through all other elements for ( var i=3; i<n; i++) sum[i] = arr[i] + minimum(sum[i-3], sum[i-2], sum[i-1]); return minimum(sum[n-1], sum[n-2], sum[n-3]); } // Driver code var arr = [1, 2, 3, 20, 2, 10, 1]; var n = arr.length; document.write( "Min Sum is " + findMinSum(arr, n)); </script> |
Min Sum is 4
Time Complexity : O(n)
Auxiliary Space : O(n), since n extra space has been taken.
This problem and solution are contributed by Ayush Saluja.