Minimum value to be added to the prefix sums at each array indices to make them positive

0 0 4 minutes read

Given an array arr[] consisting of N of integers, the task is to find the minimum positive value S that needs to be added such that the prefix sum at each index of the given array after adding S is always positive.

Examples:

Input: arr[] = {-3, 2, -3, 4, 2}
Output: 5
Explanation:
For S = 5, prefix sums at each array indices are as follows:
At index 1: (5 – 3) = 2
At index 2: (2 + 2) = 4
At index 3: (4 – 3) = 1
At index 4: (1 + 4) = 5
At index 5: (5 + 2) = 7
Since all the prefix sums obtained is greater than 0, the required answer is 5.

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

Naive Approach: The simplest approach is to iterate over all possible values of S starting from 1, and add S to the prefix sum at each array indices and check if it is greater than 0 or not. Print that value of S for which all the prefix sums are found to be positive.

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, follow the steps below:

Initialize a variable minValue with 0 to store the minimum prefix sum.
Initialize a variable sum to store the prefix sum at every index.
Traverse the array arr[] over range [0, N – 1] using the variable i.
- Update the sum and add arr[i] to the sum.
- If sum is less than minValue, set minValue as sum.
Initialize a variable startValue to store the desired result and set startValue equal to (1 – minValue).
After the above steps, print the value of startValue as minimum possible value of S.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum startValue
// for positive prefix sum at each index
int minStartValue(vector<int>& nums)
{
    // Store the minimum prefix sum
    int minValue = 0;
 
    // Stores prefix sum at each index
    int sum = 0;
 
    // Traverse over the array
    for (auto n : nums) {
 
        // Update the prefix sum
        sum += n;
 
        // Update the minValue
        minValue = min(minValue, sum);
    }
 
    int startValue = 1 - minValue;
 
    // Return the positive start value
    return startValue;
}
 
// Driver Code
int main()
{
    vector<int> nums = { -3, 2, -3, 4, 2 };
 
    // Function Call
    cout << minStartValue(nums);
 
    return 0;
}

Java

// Java program for the
// above approach
import java.util.*;
 
class GFG{
 
// Function to find minimum startValue
// for positive prefix sum at each index
static int minStartValue(int[] nums)
{
     
    // Store the minimum prefix sum
    int minValue = 0;
  
    // Stores prefix sum at each index
    int sum = 0;
     
    // Traverse over the array
    for(int n : nums)
    {
         
        // Update the prefix sum
        sum += n;
         
        // Update the minValue
        minValue = Math.min(minValue, sum);
    }
     
    int startValue = 1 - minValue;
     
    // Return the positive start value
    return startValue;
}
  
// Driver Code
public static void main(String[] args)
{
    int[] nums = { -3, 2, -3, 4, 2 };
  
    // Function Call
    System.out.println(minStartValue(nums));
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the
# above approach
 
# Function to find minimum startValue
# for positive prefix sum at each index
def minStartValue(nums):
   
    # Store the minimum prefix sum
    minValue = 0
 
    # Stores prefix sum at each index
    sum = 0
 
    # Traverse over the array
    for i in range(len(nums)):
       
        # Update the prefix sum
        sum += nums[i]
 
        # Update the minValue
        minValue = min(minValue, sum)
 
    startValue = 1 - minValue
     
    # Return the positive start value
    return startValue
 
# Driver Code
if __name__ == '__main__':
   
    nums = [ -3, 2, -3, 4, 2 ]
     
    # Function Call
    print(minStartValue(nums))
 
# This code is contributed by Princi Singh

C#

// C# program for the above approach
using System;
  
class GFG{
   
// Function to find minimum startValue
// for positive prefix sum at each index
static int minStartValue(int[] nums)
{
      
    // Store the minimum prefix sum
    int minValue = 0;
   
    // Stores prefix sum at each index
    int sum = 0;
      
    // Traverse over the array
    foreach(int n in nums)
    {
          
        // Update the prefix sum
        sum += n;
          
        // Update the minValue
        minValue = Math.Min(minValue, sum);
    }
      
    int startValue = 1 - minValue;
      
    // Return the positive start value
    return startValue;
}
   
// Driver Code
public static void Main()
{
    int[] nums = { -3, 2, -3, 4, 2 };
   
    // Function Call
    Console.WriteLine(minStartValue(nums));
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
// Javascript program for the above approach
 
// Function to find minimum startValue
// for positive prefix sum at each index
function minStartValue(nums)
{
 
    // Store the minimum prefix sum
    let minValue = 0;
 
    // Stores prefix sum at each index
    let sum = 0;
 
    // Traverse over the array
    for (let n = 0; n < nums.length; n++) {
 
        // Update the prefix sum
        sum += nums[n];
 
        // Update the minValue
        minValue = Math.min(minValue, sum);
    }
    let startValue = 1 - minValue;
 
    // Return the positive start value
    return startValue;
}
 
// Driver Code
    let nums = [ -3, 2, -3, 4, 2 ];
 
    // Function Call
    document.write(minStartValue(nums));
     
    // This code is contributed by souravmahato348.
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!