CODEWITHSUNDEEP
algorithmmath
now he who must not be named.
now he who must not be named.

Reputation: 9396

Finding the minimum number which when added to running sum of array is 1

Starting with a given array of integers and a value 'x'. Calculate the running sum of x plus each array element, from left to right. The running sum must never get below 1. Determine the minimum value of x.

For eg. arr = [-2, 3, 1, -5].

If x = 4, the following results are obtained:

Running     
sum       arr[i]
-----     -----
4          -2
2           3
5           1
6          -5
1

Any ideas how to find this. I tried starting from '0' and slowly incrementing until we reach 1, but thats a wrong approach, I guess.

Upvotes: 2

Views: 23889

Answers (5)

Hà Huy Giáp
Hà Huy Giáp

Reputation: 1

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minX(vector<int> &arr)
{
    vector<int> temp;
    int sumwX = 1;
    for(auto it = arr.begin(); it != arr.end(); ++it)
    {
        sumwX += *it;
        temp.push_back(sumwX);
    }
    
    return (1 - (*min_element(temp.begin(), temp.end()) - 1 ));
}

int main()
{
    
    vector<int> M = {-5,4,-2,3,29,-1,-6,-1,0,-5};
    vector<int> N = {-2,3,1,-5};
    vector<int> V = {-5,4,-2,3,1,-1,-6,-1,0,-5};
    cout << minX(M) << endl;
    cout << minX(N) << endl;
    cout << minX(V) << endl;
    return 0;
}

Upvotes: 0

Ronit
Ronit

Reputation: 1

def minX(arr):
    temp,count1,counter,found= 1,2,len(arr)-1,False
    while  counter !=-1 :
        temp+=(arr[counter] * -1)
        counter -=1
        if temp < 1 :
            temp = 0
            temp += count1
            count1 += 1
            counter = len(arr)-1
    return temp

Upvotes: 0

Paddy3118
Paddy3118

Reputation: 4772

You can go through the array left-to-right adjusting for x as you go (Python):

In [2]: arr = [-2, 3, 1, -5]

In [3]: accum = x = 0

In [4]: for item in arr:
   ...:     accum += item
   ...:     if accum < 1:
   ...:         x += 1 - accum
   ...:         accum = 1
   ...:         

In [5]: accum
Out[5]: 1

In [6]: x
Out[6]: 4

Upvotes: 0

trincot
trincot

Reputation: 351384

Perform the accumulation in reverse, meaning:

Start with 1 and subtract values from the end of the array walking back to the the start of the array. Whenever you get a value that is less than 1, correct it to 1 before continuing the subtractions.

The value you get at completion of this algorithm is the minimum value of x you are looking for.

Implementation in a runnable JavaScript snippet:

function getMinX(arr) {
    let x = 1;
    for (let i = arr.length - 1; i >= 0; i--) {
        x = x - arr[i];
        if (x < 1) x = 1;
    }
    return x;
}

let arr = [-2, 3, 1, -5];
console.log(getMinX(arr)); // 4

Some languages support functional programming style, in which you can use a fold. In JavaScript that would be coded as:

const getMinX = arr => arr.reduceRight((x, val) => Math.max(1, x-val), 1);

console.log(getMinX([-2, 3, 1, -5])); // 4

Upvotes: 7

GoodDok
GoodDok

Reputation: 1850

You should

  1. Calculate rolling sums for the input array of integers (time O(n))
    E.g.: arr = [-2, 3, 1, -5] => arr_rolling = [0, -2, 1, 2, -3]
  2. Get the minimum element among the sums -- min_sum (time O(n))
    E.g.: arr_rolling = [0, -2, 1, 2, -3] => min_sum = -3
  3. X = 1 - min_sum (time O(1))
    E.g.: min_sum = -3 => X = 4

The final time complexity is O(n).

Once you understand the algorithm, you may notice that there's no need to store rolling sums and you can calculate rolling sum minimum "on the fly". Once you notice it, the memory usage becomes O(1).

Upvotes: 2

Related Questions