સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવાનું ન્યૂનતમ મૂલ્ય


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સ્વિગી
અરે

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને સંખ્યાઓનો ક્રમ આપવામાં આવે છે (સકારાત્મક નકારાત્મક અથવા શૂન્ય હોઈ શકે છે). આપણે અમારી સાથે સકારાત્મક પૂર્ણાંક લેવો પડશે અને પછી અમે આના બધા પૂર્ણાંકો ઉમેરવાનું શરૂ કરીશું એરે તેની સાથે ડાબેથી જમણે.
અમે ન્યૂનતમ સકારાત્મક પૂર્ણાંકો જોઈએ છે જે આપણે શરૂઆતમાં લેવું જોઈએ, જેથી કોઈપણ સમયે આપણી વર્તમાન રકમ હંમેશા હકારાત્મક રહે.

ઉદાહરણ

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

સમજૂતી:

સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવાનું ન્યૂનતમ મૂલ્ય
આપણે અહીં જોઈ શકીએ છીએ કે જો આપણે સ્ટાર્ટવalલ્યુ = 5 પસંદ કરીએ, તો આપણે બધી મધ્યવર્તી રકમ સકારાત્મક મેળવીશું. આપણે startValue = 4 પણ ચકાસી શકીએ છીએ, જે યોગ્ય સોલ્યુશન નથી.

nums = [1,2]
1

સમજૂતી:

ન્યૂનતમ પ્રારંભિક મૂલ્ય હકારાત્મક હોવું જોઈએ.

અભિગમ

માની લો, આપણી પાસે એરે છે, નંબર્સ = [-3,2, -3,4,2]
હવે જો આપણે પ્રારંભિક મૂલ્ય 2 તરીકે પસંદ કરીએ, અને ડાબેથી જમણે તત્વો ઉમેરવાનું ચાલુ રાખીએ, તો:

સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવાનું ન્યૂનતમ મૂલ્ય

ઉપરના ઉદાહરણમાં, આપણે પ્રારંભિક મૂલ્ય 2 તરીકે પસંદ કર્યું છે. આપણી રકમ દર વખતે સકારાત્મક રહેશે નહીં, તેથી અમને કેટલાક મોટા તત્વોની જરૂર છે.

પ્રારંભિક વેલ 5 થવા દો.
સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવાનું ન્યૂનતમ મૂલ્ય
હવે, આપણે સ્પષ્ટ રીતે જોઈ શકીએ છીએ કે જો પ્રારંભિક મૂલ્ય 5 છે, તો આપણે આપણી વર્તમાન રકમ હંમેશા હકારાત્મક રાખીને એરેમાં પ્રવાસ કરી શકીએ છીએ. 5 જવાબ હોઈ શકે જો તે કરવામાં નાનામાં પૂર્ણાંકો હોય.
ચાલો પરિસ્થિતિનો વિચાર કરીએ જો આપણે શરૂઆતમાં અમારી સાથે વ valલ = 0 પસંદ કરીએ.

સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવાનું ન્યૂનતમ મૂલ્ય

હવે, આપણે કહી શકીએ કે જો આપણે મોટાભાગના નકારાત્મક વર્તમાન રકમ (વર્તમાન ઉદાહરણમાં -4) ની કિંમતને પહોંચી વળીએ, તો પછી આપણે કોઈપણ સમસ્યા વિના સ્પષ્ટ રીતે એરે પસાર કરી શકીશું.
જેમ કે, ઉપરના ઉદાહરણમાં, સૌથી નકારાત્મક મૂલ્ય -4 છે, તેને દૂર કરવા માટે, આપણે તેને 1 બનાવવું પડશે (કારણ કે, નાનામાં સકારાત્મક પૂર્ણાંકો આવશ્યક છે).

તેથી આપણે સૌથી નકારાત્મક પરિસ્થિતિ પસાર કરવા માટે 1 - (- 4) = 5 જોઈએ છે.
આપણે એ પણ જોયું છે કે 5 સોલ્યુશન પસાર કરી શકે છે.

અને જો ત્યાં કોઈ નકારાત્મક વર્તમાન રકમ નથી, તો આપણે ફક્ત 1 આઉટપુટ કરીશું કારણ કે આપણે સકારાત્મક અભિન્ન સમાધાન જોઈએ છે.

તેથી, અમારું અલ્ગોરિધમ હશે:

1. આપણે મોટાભાગના નકારાત્મક સમાધાનની શોધ કરવી પડશે, તેથી અમે આખા એરેને પસાર કરીશું.
2. ની દરેક પુનરાવૃત્તિ માં લૂપ અમે તપાસ કરીશું કે વર્તમાન રકમ લઘુતમ છે કે નહીં અને અમે તે મુજબ અમારી ન્યુનત્તમ મૂલ્યને અપડેટ કરીશું.
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

સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવા માટે ન્યૂનતમ મૂલ્ય માટે જાવા પ્રોગ્રામ

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

સ્ટેપ Sum લીટકોડ સોલ્યુશન દ્વારા સકારાત્મક પગલું મેળવવા માટે ન્યૂનતમ મૂલ્ય માટેની જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): કારણ કે, અમે આપેલ એરેને રેખીય રીતે પસાર કરી રહ્યા છીએ, આમ અમારી સમયની જટિલતા O (n) હશે.

અવકાશ જટિલતા 

ઓ (1): અમે કોઈ વધારાની જગ્યાનો ઉપયોગ કર્યો નથી, આમ અમારી અવકાશ જટિલતા સતત રહેશે.