स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्य


अडचण पातळी सोपे
वारंवार विचारले स्विगी
अरे

समस्या विधान

या समस्येमध्ये, आम्हाला संख्यांचा क्रम दिलेला आहे (सकारात्मक नकारात्मक किंवा शून्य असू शकतो). आम्हाला आपल्या बरोबर एक सकारात्मक पूर्णांक घ्यावा लागेल आणि त्यानंतर आपण त्याचे सर्व पूर्णांक जोडण्यास सुरवात करू अॅरे त्यासह डावीकडून उजवीकडे.
आम्हाला सुरुवातीस किमान सकारात्मक पूर्णांक हवा आहे जेणेकरून आपली वर्तमान रक्कम कधीही सकारात्मक राहील.

उदाहरण

nums = [-3,2,-3,4,2]
5

स्पष्टीकरण:

स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्य
आम्ही येथे पाहू शकतो की जर आपण स्टार्टवॅल्यू = 5 निवडत असाल तर आपल्याला सर्व दरम्यानचे सम सकारात्मक मिळतात आपण स्टार्टवॅल्यू = 4 देखील तपासू शकतो, जो योग्य तोडगा नाही.

nums = [1,2]
1

स्पष्टीकरण:

किमान प्रारंभ मूल्य सकारात्मक असावे.

दृष्टीकोन

समजा, आपल्याकडे अ‍ॅरे आहेत, संख्या = [-3,2, -3,4,2]
जर आपण प्रारंभिक मूल्य 2 म्हणून निवडले आणि डावीकडून उजवीकडे घटक जोडणे सुरू ठेवले तर:

स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्य

वरील उदाहरणात, आम्ही प्रारंभिक मूल्य 2 म्हणून निवडले आहे. आमची बेरीज प्रत्येक वेळी सकारात्मक राहणार नाही, म्हणून आम्हाला काही मोठ्या घटकाची आवश्यकता आहे.

प्रारंभिक व्हॅल्यू 5 असू द्या.
स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्य
आता आपण स्पष्टपणे पाहू शकतो की जर प्रारंभ मूल्य 5 असेल तर आपण आपली सध्याची बेरीज नेहमी सकारात्मक ठेवून अ‍ॅरेमधून प्रवास करू शकतो. 5 हे सर्वात लहान पूर्णांक असल्यास असे उत्तर असू शकते.
सुरूवातीस आम्ही आमच्यासह व्हॅल = 0 निवडल्यास एखाद्या परिस्थितीचा विचार करूया.

स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्य

आता आपण असे म्हणू शकतो की जर आम्ही सर्वात नकारात्मक वर्तमान बेरीज (वर्तमान उदाहरणात -4) च्या मूल्यावर विजय मिळविला तर आपण कोणतीही समस्या न घेता अ‍ॅरे स्पष्टपणे पास करू शकतो.
प्रमाणे, वरील उदाहरणात, सर्वात नकारात्मक मूल्य -4 आहे, त्यावर मात करण्यासाठी आपल्याला ते 1 केले पाहिजे (कारण सर्वात लहान सकारात्मक पूर्णांक आवश्यक आहे).

तर सर्वात नकारात्मक परिस्थितीतून जाण्यासाठी आम्हाला 1 - (- 4) = 5 पाहिजे.
आपण हे देखील पाहिले आहे की 5 सोल्यूशन पास करू शकते.

आणि जर कोणतीही नकारात्मक वर्तमान बेरीज नसेल तर आम्ही फक्त 1 आउटपुट करू कारण आम्हाला सकारात्मक अविभाज्य तोडगा पाहिजे आहे.

तर, आमचा अल्गोरिदम असेलः

1. आम्हाला बर्‍याच नकारात्मक निराकरणाचा शोध घ्यावा लागेल, जेणेकरून आम्ही संपूर्ण अ‍ॅरे पार करू.
२ च्या प्रत्येक पुनरावृत्तीमध्ये लूप आम्ही वर्तमान बेरीज किमान आहे की नाही ते तपासू आणि त्यानुसार आमचे किमान मूल्य अद्यतनित करू.
Finally. शेवटी हे सर्वात नकारात्मक मूल्य 3 करण्यासाठी, आपण ते फक्त 1 वजा करू. (उदा. जर मि = = 1, व्हॅल = 4 - (- 1) = 4).

अंमलबजावणी

स्टेप बेम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्यासाठी सी ++ प्रोग्राम

#include <iostream>
#include<vector>
using namespace std;

int minStartValue(vector<int>& nums) {
    
    int min=0,sum=0;
    for (int i = 0; i < nums.size(); i++){
        sum+=nums[i];
        min=min<sum?min:sum;
    }
    
    return 1-min;
}

int main() {
    vector<int> nums{-3,2,-3,4,2}; 
    cout<<minStartValue(nums)<<endl;	
  return 0;
}
5

स्टेप सम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्यासाठी जावा प्रोग्राम

import java.util.*;

class Rextester{
    
    public static int minStartValue(int[] nums) 
    {
        Integer min=0,sum=0;
        for(int i:nums){
            sum+=i;
            min=Math.min(min,sum);
        }
        return 1-min;
    }
    
    public static void main(String args[])
    {
       	int[]nums={-3,2,-3,4,2};
        int ans=minStartValue(nums);
        System.out.println(ans);
    }
}
5

स्टेप सम लेटकोड सोल्यूशनद्वारे सकारात्मक चरण मिळविण्यासाठी किमान मूल्यासाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): कारण आम्ही दिलेली अ‍ॅरे रेषेचा मागोवा घेत आहोत, त्यामुळे आमची वेळ गुंतागुंत ओ (एन) होईल.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): आम्ही कोणतीही जास्तीची जागा वापरली नाही, त्यामुळे आमची जागा गुंतागुंत स्थिर राहील.