CODEWITHSUNDEEP
arraysalgorithmarray-algorithms
Himanshu Saxena
Himanshu Saxena

Reputation: 19

Given an array of numbers, find a number to start with such that the sum is never negative

Given an array of integers, find the smallest number X to start with, such that adding elements of array to X, the sum is always greater than 0

If given array is {-2, 3, 1, -5} For example, in the above array, X should be 4

Explanation: If, we start with 4, then adding first number -2, array sum becomes 4 + (-2) = 2 (which is >0) Now adding next element 3 to current sum which is 2, 2+ 3 = 5 (which is >0) Adding next element 1 to new sum 5 gives, 5 + 1 = 6 (which is >0) Adding last element -5 to new sum 6 gives 6 + (-5) = 1, which is again greater than zero.

Given an array of integers, How can I find the smallest number X?

Upvotes: 0

Views: 1638

Answers (4)

Prajjwal Pandey
Prajjwal Pandey

Reputation: 21

This problem can be solved with the simple logic by precomputing the sum of all the elements present in the array.

Find the Sum of all the elements present in the array.

If sum equals zero return 1 as it will give smallest number on adding which we will get the total sum greater than zero.

If sum greater than zero return a negative number just less than that sum ( handle the special case of sum == 1 seperately)

If sum is negative then return the positive number just one greater than the sum in magnitude.

Step 1 : Find the Sum of all the Elements in the array

 int sum = 0;
for(int i = 0; i < arr.size(); i++)
 {
         sum += arr[i];
 }

Step 2 : Check The Sum obtained and Apply the following logic

if(sum == 0)
         return 1;
else if( sum < 0)
         return abs(sum)+1;
else 
        {
               if( sum == 1)
                          return 0;
               else
                         return  -(sum-1);

         }

Upvotes: 0

Vishal_898
Vishal_898

Reputation: 300

First we should check if element at ith position is greater than zero or not. If element is greater than zero then no problem and we can add it directly to our sum, ans remains unchanged. But if not greater than zero then we first check whether sum is greater than element or not. If sum is greater than abs(arr[I]) then then we decrease our sum by abs(arr[I]), ans remains unchanged but if abs(arr[I]) is greater than sum then we add abs(arr[i]-sum+1) to ans and initialise sum to 1.

Below is code for same: 

 #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main()
    {
        // considering x>=0(x can't take values less than 0)
        ll arr[] = { -2, 3, 1, -5};
        ll n = sizeof(arr) / sizeof(ll);
        ll ans = 0; // My answer
        ll sum = 0; // current sum of elements
        for (ll i = 0; i < n; i++)
        {
            if (arr[i] <= 0)
            {
                if ((sum + arr[i]) <= 0)
                {
                    ans += (abs(sum + arr[i]) + 1); //add 1 to make sum=1
                    sum = 1;
                }
                else
                    sum += arr[i];   // added because arr[i]<=0,(sum-=abs(arr[i]))
            }
            else
                sum += arr[i];
        }
        cout << ans;

        return 0;
    }
    // ans=4 for this case

Upvotes: 1

MBo
MBo

Reputation: 80107

Find minimum of cumulative sum for given array.
Needed result is 1 - MinC

A = [-2, 3, 1, -5]
CSum = 0
MinC = 10000000000
for x in A:
    CSum += x
    MinC = min(MinC, CSum)
Addend = 1 - MinC
print(Addend)

>>> 4

Upvotes: 2

Mr Sukhe
Mr Sukhe

Reputation: 77

you should find miniminum subarray sum first. lets say it comes equal to k. your answer should be k+1. you can find minimum sum here : https://www.geeksforgeeks.org/smallest-sum-contiguous-subarray/

Upvotes: 0

Related Questions