1413. Minimum Value to Get Positive Step by Step Sum

leetcode easy

#array#csharp#easy#leetcode

Task

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.

Пример:

Input: nums = [-3,2,-3,4,2]

Output: 5

Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.

step by step sum

startValue = 4 | startValue = 5 | nums

(4 -3 ) = 1 | (5 -3 ) = 2 | -3

(1 +2 ) = 3 | (2 +2 ) = 4 | 2

(3 -3 ) = 0 | (4 -3 ) = 1 | -3

(0 +4 ) = 4 | (1 +4 ) = 5 | 4

(4 +2 ) = 6 | (5 +2 ) = 7 | 2

C# solution

matched/original

public class Solution {
    public int MinStartValue(int[] nums) {
        int startValue = 1;
        while (true) {
            int total = startValue;
            bool isValid = true;
            foreach (int num in nums) {
                total += num;
                if (total < 1) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return startValue;
            }
            startValue += 1;
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinStartValue(vector<int>& nums) {
        int startValue = 1;
        while (true) {
            int total = startValue;
            bool isValid = true;
            foreach (int num in nums) {
                total += num;
                if (total < 1) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return startValue;
            }
            startValue += 1;
        }
    }
}

Java solution

matched/original

class Solution {
    public int minStartValue(int[] nums) {
        int startValue = 1;

        while (true) {
            int total = startValue;
            boolean isValid = true;

            for (int num : nums) {
                total += num;

                if (total < 1) {
                    isValid = false;
                    break;
                }
            }

            if (isValid) {
                return startValue;
            } else {
                startValue += 1;
            }
        }
    }
}

JavaScript solution

matched/original

var minStartValue = function(nums) {
    let startValue = 1;
    while (true) {
        let total = startValue;
        let isValid = true;
        for (let num of nums) {
            total += num;
            if (total < 1) {
                isValid = false;
                break;
            }
        }
        if (isValid) {
            return startValue;
        }
        startValue++;
    }
};

Python solution

matched/original

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        startValue = 1
        while True:
            total = startValue
            isValid = True
            for num in nums:
                total += num
                if total < 1:
                    isValid = False
                    break
            if isValid:
                return startValue
            startValue += 1

Go solution

matched/original

func minStartValue(nums []int) int {
    startValue := 1
    for {
        total := startValue
        isValid := true
        for _, num := range nums {
            total += num
            if total < 1 {
                isValid = false
                break
            }
        }
        if isValid {
            return startValue
        }
        startValue++
    }
}

Explanation

Algorithm

Инициализируйте переменные startValue со значением 1 и total со значением startValue.

Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎