EJMAR21H - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shekhar Srivastava
Tester: Akash Kumar Bhagat

DIFFICULTY:

CAKEWALK

PROBLEM:

Given an array of integers you have to find the smallest value you need to initialize your sum variable with so that when you use this variable to calculate the cumulative sum of the array the value of this variable is a natural number in every step.

EXPLANATION:

keep two variables, say, min_initial_value = 0 and running_sum = 0.
start adding the integers to the variable running_sum, every time its value goes below 1, add the amount you need to add to it to make it 1 to the variable min_initial_value and set the value of running_sum to 1. you will have your answer in min_initial_value.

for example, if the array of integers is [1, 2, 0, -1, -5, 10]
till 4th element the sum is 2, then on adding -5 the sum becomes -3
at this point we need to add 4(our answer to this example) to get 1. then on adding 10 the sum is 11. so we need to initialize our sum with 4 and the corresponding running sum will be:
[5, 7, 7, 6, 1, 11].

since we need to go through the elements of the array once, the time complexity is O(n) (per test-case) where n is the number of elements in the integer array.

SOLUTIONS:

python
def solution():
    t = int(input())
    # assert 1<=t<=100
    for _ in range(t):
        n = int(input())
        # assert 1<=n<=1000
        s = 0 
        miv = 0
        for i in map(int, input().split()):
            # assert -1000<=i<=100
            s+=i 
            if s<1:
                miv += 1-s 
                s = 1 
        print(miv)
solution()

python (alernate solution)
# find the minimum value that occurs in the original running sum (min_val), 
# if it is less than 1, the answer is 1- min_val else 0
for _ in range(int(input())):
    n=int(input())
    a=[int(i) for i in input().split()]
    c=0
    m=float('inf')
    for i in a:
        c+=i
        m=min(m,c)
    print(max(1-m,0))

c++
#include<bits/stdc++.h>
using namespace std;
#include<vector>
#include<iterator>
#define ll long long 
#define vll vector<ll>
#define vi vector<int>
void solve(){
	int n,p,ans=0,sums=0;
    cin>>n;
	while(n--){
		cin>>p;
		sums+=p;
		if(sums<=0) {
			ans+=(1-sums);
			sums=1;
		}
	}
	cout<<ans<<"\n";
}
 
int main(){
 
	int tc;
	cin>>tc;
	while(tc--){
		solve();
	}
	return 0;
}