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(N2)
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 indexint 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 Codeint main(){ vector<int> nums = { -3, 2, -3, 4, 2 }; // Function Call cout << minStartValue(nums); return 0;} |
Java
// Java program for the// above approachimport java.util.*;class GFG{// Function to find minimum startValue// for positive prefix sum at each indexstatic 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 Codepublic 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 indexdef 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 Codeif __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 approachusing System; class GFG{ // Function to find minimum startValue// for positive prefix sum at each indexstatic 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 Codepublic 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 indexfunction 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:
5
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
