Given an array arr[] of positive numbers, the task is to find the minimum sum of a subsequence of maximum possible elements with the constraint that no two numbers in the sequence are adjacent.
Examples:
Input: arr[]={1, 7, 3, 2}
Output: 3
Explanation: Pick the subsequence {1, 2}.
The sum is 3 and no two elements are adjacent.
This is the least possible sum.Input: arr[]={1, 8, 4, 10, 6}
Output: 11
Explanation: Pick the subsequence {1, 4, 6}.
The sum is 11 and no two elements are adjacent.
This is the least possible sum.Input: arr[]={2, 0, 11, 2, 0, 2}
Output: 4
Explanation: Pick the subsequence {0, 2, 2}.
The sum is 4 and no two elements are adjacent.
This is the least possible sum.
Approach: To solve the problem follow the below observations:
There are two different cases:
- Array size is Odd – the only choice is to pick the even indexed elements(Zero – Based Indexing).
- Array size is Even – The subsequence size will be N/2. It can be in three possible ways
- All the even indexed elements.
- All the odd indexed elements.
- Even indexed elements till i and odd indexed elements starting from i+3
- The minimum among these 3 will be the answer.
Follow the steps to solve the problem:
- If the size of arr[] is Odd, the sum of all the even indexed elements is the answer.
- For Size of arr to Even, store the sum of all the even indices into a variable.
- Iterating from the end by adding the odd index elements and removing the even indexed elements from the end.
- Update the minimum answer in each index.
- After the iteration is over, return the minimum value as the answer.
Below is the implementation of the above approach.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find the minimum sumint FindMinSum(vector<int>& vec, int n){ int sum = 0; for (int i = 0; i < n; i += 2) { // Sum of all the even indices sum += vec[i]; } if (n % 2 != 0) return sum; int ans = sum; for (int i = n - 1; i > 0; i -= 2) { // Removing the even index and // addinig the odd index sum = sum - vec[i - 1] + vec[i]; // Checking for the minimum sum ans = min(sum, ans); } // Return the minimum sum return ans;}// Driver Codeint main(){ // Creating the array vector<int> arr = { 2, 0, 11, 2, 0, 2 }; int N = vec.size(); // Function call cout << FindMinSum(arr, N) << endl; return 0;} |
C
#include <stdio.h>int FindMinSum(int arr[], int n){ int sum = 0; for (int i = 0; i < n; i += 2) { // sum of all the odd indexes sum += arr[i]; } if (n % 2 == 1) return sum; int ans = sum; for (int i = n - 1; i > 0; i -= 2) { // removing the odd index and addinig the even index sum = sum - arr[i - 1] + arr[i]; // checking for the minimum sum if (sum < ans) ans = sum; } // Return the minimum sum return ans;}// Driver Codeint main(){ // Creating the array int arr[] = { 2, 0, 11, 2, 0, 2 }; int n = *(&arr + 1) - arr; // Function call int answer = FindMinSum(arr, n); printf("%d", answer); return 0;} |
Java
import java.io.*;import java.util.*;public class GFG { static int solve(int vec[], int n) { int sum = 0; if (n % 2 != 0) { for (int i = 0; i < n; i = i + 2) { // sum of all the odd indexes sum = sum + vec[i]; } return sum; } else { int ans = sum; for (int i = n - 1; i > 0; i -= 2) { // removing the odd index and addinig the // even index ans = ans - vec[i - 1] + vec[i]; // checking for the minimum sum ans = Math.min(ans, sum); } // Return the minimum sum return ans; } } public static void main(String args[]) throws IOException { // Creating the array int vec[] = { 2, 1, 2 }; int n = vec.length; // Function call System.out.println(solve(vec, n)); }} |
Python
# Python code to implement the approachdef FindMinSum(list, n): sum = 0 for i in range(0, n, 2): # sum of all the odd indexes sum = sum + list[i] if n % 2 == 1: return sum ans = sum for i in range(n-1, 0, -2): # removing the odd index and addinig the even index sum = sum - list[i-1] + list[i] # checking for the minimum sum ans = min(sum, ans) # Return the minimum sum return ans# Driver Code# Creating the listlist = [2, 0, 11, 2, 0, 2]n = 6# Function callk = FindMinSum(list, n)print(k) |
C#
// C# code for the above approach:using System;public class GFG { static int solve(int[] vec, int n) { int sum = 0; if (n % 2 != 0) { for (int i = 0; i < n; i = i + 2) { // sum of all the odd indexes sum = sum + vec[i]; } return sum; } else { int ans = sum; for (int i = n - 1; i > 0; i -= 2) { // removing the odd index and addinig the // even index ans = ans - vec[i - 1] + vec[i]; // checking for the minimum sum ans = Math.Min(ans, sum); } // Return the minimum sum return ans; } } // Driver Code static public void Main() { // Creating the array int[] vec = { 2, 1, 2 }; int n = vec.Length; // Function call Console.WriteLine(solve(vec, n)); }}// This code is contributed by Rohit Pradhan |
Javascript
<script> // JavaScript code for the above approach: // Function to find the minimum sum const FindMinSum = (vec, n) => { let sum = 0; for (let i = 0; i < n; i += 2) { // Sum of all the even indices sum += vec[i]; } if (n % 2 != 0) return sum; let ans = sum; for (let i = n - 1; i > 0; i -= 2) { // Removing the even index and // addinig the odd index sum = sum - vec[i - 1] + vec[i]; // Checking for the minimum sum ans = Math.min(sum, ans); } // Return the minimum sum return ans; } // Driver Code // Creating the array let arr = [2, 0, 11, 2, 0, 2]; let N = arr.length; // Function call document.write(FindMinSum(arr, N));// This code is contributed by rakeshsahni</script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
