1 ડી એરે લીટકોડ સોલ્યુશનનો સરવાળો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ઉબેર
અરે

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

1d ની ચાલી રહેલ રકમમાં એરે સમસ્યા આપણને એરે નંબર્સ આપવામાં આવ્યા છે જેના માટે આપણે એરે પરત આપવી પડશે જ્યાં પરિણામ એરે એરેના દરેક અનુક્રમણિકા માટે હું [i] = સરવાળા (સંખ્યાઓ [0]… નંબર્સ [i]).

ઉદાહરણ

 nums = [1,2,3,4]
[1,3,6,10]

સમજૂતી:

ચાલી રહેલ રકમ: [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4] = [1, 3, 6, 10]

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

સમજૂતી:

ચાલી રહેલ રકમ એ છે: [1, 1 + 1, 1 + 1 + 1, 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1] = [1, 2, 3, 4, 5]

અભિગમ

આ સમસ્યામાં આપણે એરે બનાવવી પડશે જ્યાં આપેલ એરેમાં તત્વોનું મૂલ્ય 1 લી થી આઇથ ઇન્ડેક્સ્ડ તત્વ માટેના તત્વોની રકમ સમાન હશે.
આ માટે આપણે આપેલ એરે સાઈઝની સમાન સાઇઝની એરે બનાવી શકીએ છીએ. પછી લૂપ માટેના દરેક તત્વ માટે આપણે લૂપ માટે બીજાનો ઉપયોગ કરીને મૂળ એરેમાં અનુક્રમણિકા 0 થી અનુક્રમણિકા i ને તત્વ ઉમેરી શકીએ. આ અલ્ગોરિધમનો સમય જટિલતા ઓ (n ^ 2) હશે.

અમે ફક્ત એકલનો ઉપયોગ કરીને આ સમસ્યા માટેની સમયની જટિલતાને ઘટાડી શકીએ છીએ લૂપ.
ચાલો નંબરો આપેલ એરે હોઈએ અને રેઝ એરે બનીએ જેમાં આપણે ચાલી રહેલ રકમ સ્ટોર કરી રહ્યા છીએ, તો પછી આપણે રેઝ [i] ની ગણતરી નીચે મુજબ કરી શકીએ:

res [i] = res [i-1] + nums [i].

ઉદાહરણ: નંબર્સ = [1,2,3,4] નીચેની આકૃતિમાં બતાવવામાં આવ્યા છે,

1 ડી એરે લીટકોડ સોલ્યુશનનો સરવાળો

તેથી આપણે ફરીથી પ્રીફિક્સ સરવાળાની ગણતરી કરવા માટે લૂપ ચલાવવાની જરૂર નથી, કારણ કે રેસા એરેના પાછલા અનુક્રમણિકામાં મેં સંગ્રહિત અનુક્રમણિકા સુધી પહેલાથી જ સરવાળો આપ્યો છે.

અમલીકરણ

1 ડી એરે લીટકોડ સોલ્યુશનનો સરવાળો ચલાવવા માટે સી ++ પ્રોગ્રામ

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

vector<int> runningSum(vector<int>& nums) 
{
    vector<int> res(nums.size());
    if(nums.size()==0) return res;

    res[0]=nums[0];
    for(int i=1;i<nums.size();i++)
    {
        res[i]=res[i-1]+ nums[i];
    }

    return res;

}

int main() 
{
  vector<int> nums={1,2,3,4};
  vector<int> res= runningSum(nums);
  
  cout<<"[";
  
  for(int i=0;i<res.size()-1;i++) cout<<res[i]<<",";
  
  cout<<res.back()<<"]"<<endl;

  return 0; 
}
[1,3,6,10]

1 ડી એરે લીટકોડ સોલ્યુશનનો સરવાળો ચલાવવા માટે જાવા પ્રોગ્રામ

import java.lang.*;

class Rextester
{  
    public static int[] runningSum(int[] nums) 
    {
        int[] res= new int[nums.length];
        if(nums.length==0) return res;

        res[0]=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            res[i]=res[i-1]+ nums[i];
        }

        return res;
    }
    
    public static void main(String args[])
    {
        int nums[]={1,2,3,4};
        int res[]= runningSum(nums);

        System.out.print("[");

        for(int i=0;i<res.length-1;i++) System.out.print(res[i]+",");

        System.out.println( res[res.length-1] + "]");
        
    }
}
[1,3,6,10]

1 ડી એરે લીટકોડ સોલ્યુશનનો સરવાળો ચલાવવા માટેની જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): જ્યાં n આપેલ એરેનું કદ છે. જેમ આપણે લૂપ માટે ફક્ત એક જ ચલાવીએ છીએ, તેથી સમય જટિલતા રેખીય હશે.

અવકાશ જટિલતા 

ઓ (એન): અહીં આપણે n ના કદનો પરિણામ એરે બનાવી રહ્યા છીએ. તેથી જગ્યા જટિલતા પણ રેખીય હશે.