[Solved] Negative Prefix C++,Java, Python

Given an array A[] of N integers. In each operation, Geek can increase the i^th element by 1 (i.e set A[i] = A[i]+1 where 1 < i < N).The task is to calculate the minimum number of operations required such that there is no prefix in the array A[] whose sum is less than zero. (i.e For all i, This condition should be satisfied A[1]+A[2]+…A[i] > 0 ). 

Example 1:Input: N = 3 A[] = {2, -3, 1} Output: 1 Explanation: Geek can increase the 2nd element of the array by 1.

Example 2:Input: N = 1 A[] = {5} Output: 0 Explanation: No operations required.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function minOperations() which takes the array A[], its size N, and returns the minimum number of operations.

Constraints:
1 < N < 10⁵
-10⁵ < A[i] < 10⁵

Solution

C++

//User function Template for C++
class Solution {
    public:
    long long minOperations(vector<int> A, int N) {
        // Code here
        
        long long op = 0;
       
        
       
       
     
       long long pre = A[0];
       
       if( pre < 0 ){
           op += abs( pre );
              pre += op;
       }
       for( int i = 1 ; i < N ; i ++ ){
           pre += A[i];
    
          if( pre < 0 ){
              
              op += abs( pre );
              pre += abs( pre );
             
              
          }
           
       }
       
       return op;
    }
};

Python3

#User function Template for python3
class Solution:
    def minOperations(self, A, N): 
        sum = 0
        r = 0
        
        for i in A:
            sum += i
            
            if sum < 0:
                r += abs(sum)
                sum = 0
        
        return r
        

Java

//User function Template for Java
class Solution 
{ 
    long minOperations(int A[], int N) 
    { 
        // code here
        
        long count=0;
        int temp=0;
        for(int i=0;i<N;i++)
        {
            if(A[i]>0)
              temp++;
        }
        if(temp==N)
          return 0;
        int prefix[]=new int[N];
        
        prefix[0]=A[0];
        if(A[0]<0)
        {
          prefix[0]=0;
          count=-A[0];
        }
        for(int i=1;i<N;i++)
        {
            prefix[i]=prefix[i-1]+A[i];
            if(prefix[i]<0)
            {
              count+=-prefix[i];
              prefix[i]=0;
            }
        }
        
        
        
        return count;
    }
} 

Happy Learning – If you require any further information, feel free to contact me.