Minimum sum possible by assigning every increasing/decreasing consecutive pair with values in that order
Given an array arr[] of size N, the task is to find the minimum sum of positive integers that can be assigned to each array element arr[i], such that if arr[i] > arr[i+1] or arr[i β 1], then the positive integer assigned to arr[i] must exceed the integer assigned to arr[i + 1] or arr[i β 1].
Examples:
Input: arr[] = {1, 0, 2}
Output: 5
Explanation: One possible way to assign positive integers is ans[] = {2, 1, 2} such that the following conditions are satisfied:
- arr[0] > arr[1] and ans[0] > ans[1]
- arr[1] < arr[2] and ans[1] < ans[2]
Therefore, minimum possible sum = 2 + 1 + 2 = 5.
Input: arr[] = {1, 2, 2}
Output: 4
Explanation: One possible way to assign positive integers is ans[] = {1, 2, 1}. Therefore, the minimum possible sum = 1 + 2 + 1 = 4.
Approach: The idea is to traverse the given array from left to right and from right to left to update the answer for each element arr[i] such that the answer for arr[i] is greater than the answers for arr[i+1] and arr[i β 1] if arr[i] is greater than arr[i + 1] and arr[i β 1]. Follow the below steps to solve the problem:
- Initialize a vector ans of size N that stores the minimum positive integer that can be assigned to each element.
- Initialize the vector ans with 1 as each element must be assigned some positive integer.
- Traverse the array from left to right using variable i and if arr[i] is greater than arr[i β 1] then update ans[i] as ans[i] = ans[i β 1] + 1.
- Now, traverse the array from right to left using variable i if arr[i] is greater than arr[i+1], then update ans[i] as ans[i] = max(ans[i], ans[i + 1] + 1).
- Now, find the sum of positive integers present in the vector ans and print it as the minimum possible sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the minimum sum // of values assigned to each element // of the array as per given conditions void minSum( int * arr, int n) { // Initialize vectors with value 1 vector< int > ans(n, 1); // Traverse from left to right for ( int i = 1; i < n; i++) { // Update if ans[i] > ans[i-1] if (arr[i] > arr[i - 1]) { ans[i] = max(ans[i], ans[i - 1] + 1); } } // Traverse from right to left for ( int i = n - 2; i >= 0; i--) { // Update as ans[i] > ans[i+1] // if arr[i]> arr[i+1] if (arr[i] > arr[i + 1]) { ans[i] = max(ans[i], ans[i + 1] + 1); } } // Find the minimum sum int s = 0; for ( auto x : ans) { s = s + x; } // Print the sum cout << s << endl; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call minSum(arr, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to print the // minimum sum of values // assigned to each element // of the array as per given // conditions static void minSum( int [] arr, int n) { // Initialize vectors // with value 1 int [] ans = new int [n]; Arrays.fill(ans, 1 ); // Traverse from left // to right for ( int i = 1 ; i < n; i++) { // Update if ans[i] > ans[i-1] if (arr[i] > arr[i - 1 ]) { ans[i] = Math.max(ans[i], ans[i - 1 ] + 1 ); } } // Traverse from right to left for ( int i = n - 2 ; i >= 0 ; i--) { // Update as ans[i] > ans[i+1] // if arr[i]> arr[i+1] if (arr[i] > arr[i + 1 ]) { ans[i] = Math.max(ans[i], ans[i + 1 ] + 1 ); } } // Find the minimum sum int s = 0 ; for ( int x : ans) { s = s + x; } // Print the sum System.out.print(s + "\n" ); } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 2 }; int N = arr.length; // Function Call minSum(arr, N); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the # above approach # Function to print the minimum # sum of values assigned to each # element of the array as per # given conditions def minSum(arr, n): # Initialize vectors with # value 1 ans = [ 1 ] * (n) # Traverse from left to # right for i in range ( 1 , n): # Update if ans[i] > # ans[i-1] if (arr[i] > arr[i - 1 ]): ans[i] = max (ans[i], ans[i - 1 ] + 1 ) # Traverse from right # to left for i in range (n - 2 , - 1 , - 1 ): # Update as ans[i] > # ans[i+1] if arr[i] > # arr[i+1] if (arr[i] > arr[i + 1 ]): ans[i] = max (ans[i], ans[i + 1 ] + 1 ) # Find the minimum sum s = 0 for x in ans: s = s + x # Print the sum print (s) # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 1 , 2 , 2 ] N = len (arr) # Function Call minSum(arr, N) # This code is contributed by Chitranayal |
C#
// C# program for the // above approach using System; class GFG{ // Function to print the // minimum sum of values // assigned to each element // of the array as per given // conditions static void minSum( int [] arr, int n) { // Initialize vectors // with value 1 int [] ans = new int [n]; for ( int i = 0; i < n; i++) ans[i] = 1; // Traverse from left // to right for ( int i = 1; i < n; i++) { // Update if ans[i] > ans[i-1] if (arr[i] > arr[i - 1]) { ans[i] = Math.Max(ans[i], ans[i - 1] + 1); } } // Traverse from right to left for ( int i = n - 2; i >= 0; i--) { // Update as ans[i] > ans[i+1] // if arr[i]> arr[i+1] if (arr[i] > arr[i + 1]) { ans[i] = Math.Max(ans[i], ans[i + 1] + 1); } } // Find the minimum sum int s = 0; foreach ( int x in ans) { s = s + x; } // Print the sum Console.Write(s + "\n" ); } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = {1, 2, 2}; int N = arr.Length; // Function Call minSum(arr, N); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // javascript program for the // above approach // Function to print the // minimum sum of values // assigned to each element // of the array as per given // conditions function minSum(arr, n) { // Initialize vectors // with value 1 let ans = new Array(n).fill(1); // Traverse from left // to right for (let i = 1; i < n; i++) { // Update if ans[i] > ans[i-1] if (arr[i] > arr[i - 1]) { ans[i] = Math.max(ans[i], ans[i - 1] + 1); } } // Traverse from right to left for (let i = n - 2; i >= 0; i--) { // Update as ans[i] > ans[i+1] // if arr[i]> arr[i+1] if (arr[i] > arr[i + 1]) { ans[i] = Math.max(ans[i], ans[i + 1] + 1); } } // Find the minimum sum let s = 0; for (let x in ans) { s = s + ans[x]; } // Print the sum document.write(s + "\n" ); } // Driver Code // Given array arr[] let arr = [1, 2, 2]; let N = arr.length; // Function Call minSum(arr, N); </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(N)