જનરેટેડ એરે લીટકોડ સોલ્યુશનમાં મહત્તમ મેળવો


મુશ્કેલી સ્તર સરળ
અરે

સમસ્યા પેદા થયેલ એરે લીક્સકોડ સોલ્યુશનમાં મહત્તમ મેળવો, અમને એક પૂર્ણાંક પૂરો પાડ્યો. આપેલ સિંગલ સાથે પૂર્ણાંક, આપણે પેદા થયેલ એરેમાં મહત્તમ પૂર્ણાંક શોધવાની જરૂર છે. એરે પે generationીના કેટલાક નિયમો છે. લાદવામાં આવેલા અવરોધો હેઠળ, અમારે મહત્તમ પૂર્ણાંક શોધવાની જરૂર છે જે ઉત્પન્ન થઈ શકે. નિયમો છે:

  1. એઆર [0] = 0, એઆર [1] = 1
  2. arr [2 * i] = arr [i] જ્યાં 2 <= 2 * i <= n
  3. અને એઆરઆર [2 * i + 1] = એઆરઆર [i] + એઆરઆર [i + 1] જ્યાં 2 <= 2 * હું + 1 <= n

પરંતુ ઉકેલમાં આગળ કોઈ ડાઇવ કરતા પહેલા. આપણે થોડા ઉદાહરણો પર એક નજર નાખવી જોઈએ.

જનરેટેડ એરે લીટકોડ સોલ્યુશનમાં મહત્તમ મેળવો

n = 7
3

સમજૂતી: આપેલ નિયમો અનુસાર:
સંખ્યાઓ [0] = 0, નંબરો [1] = 1
સંખ્યાઓ [(1 * 2) = 2] = સંખ્યાઓ [1] = 1
સંખ્યાઓ [(1 * 2) + 1 = 3] = નંબરો [1] + નંબરો [2] = 1 + 1 = 2
સંખ્યાઓ [(2 * 2) = 4] = સંખ્યાઓ [2] = 1
સંખ્યાઓ [(2 * 2) + 1 = 5] = નંબરો [2] + નંબરો [3] = 1 + 2 = 3
સંખ્યાઓ [(3 * 2) = 6] = સંખ્યાઓ [3] = 2
સંખ્યાઓ [(3 * 2) + 1 = 7] = નંબરો [3] + નંબરો [4] = 2 + 1 = 3

તેથી, આપણે નંબર્સ = [0,1,1,2,1,3,2,3] જોઈ શકીએ છીએ, અને તેમની વચ્ચે મહત્તમ 3 છે. આમ જવાબ is છે.

જનરેટેડ એરે લીટકોડ સોલ્યુશનમાં મહત્તમ મેળવો માટેનો અભિગમ

સમસ્યા પેદા થયેલ એરેમાં મહત્તમ મેળવો લેટકોડ સોલ્યુશનમાં કેટલીક અવરોધો છે જેને સંતોષવી આવશ્યક છે. આપેલ અવરોધો હેઠળ, અમારે મહત્તમ પૂર્ણાંક શોધવા માટે જરૂરી છે. એરે પે generationી માટેના નિયમો સમસ્યાના વર્ણનમાં પહેલાથી સમજાવી ચૂક્યા છે. ધ્યાનમાં આવતી પ્રથમ પદ્ધતિ એરેની પે generationી અને મહત્તમ તત્વ શોધવાનું છે. પરંતુ શું આ સમસ્યા હલ થશે?

જો આપણે ફક્ત પે generationી સાથે આગળ વધીએ તો અમે યોગ્ય પરિણામો શોધી શકશે નહીં. કારણ કે તેના પર આધાર રાખે છે કે આપણે એરે કેવી રીતે જનરેટ કરીએ છીએ. જ્યારે અમે ith ઇન્ડેક્સ પર હોય ત્યારે અમે 2ith અને (2i + 1) અનુક્રમણિકા પર તત્વો ઉત્પન્ન કરીએ છીએ. તે ક્ષણે, અમારી પાસે (i + 1) મી અનુક્રમણિકા માટેનું જનરેટ કરેલ મૂલ્ય નહીં હોય. તે કિસ્સામાં, પરિણામ સચોટ નહીં આવે.

સમસ્યાનું નિરાકરણ લાવવા માટે, અમે તત્વ પેદા કરવા માટેનાં સૂત્રોની હેરફેર કરીશું. જો આપણે i ને 1 માં બદલીએ, 3 જી નિયમમાં. અમને તે અરર લાગે છે કે [2 * i-1] = એઆરઆર [i] + એઆરઆર [i-1]. તેથી, હવે આપણે એરે જનરેશન માટેના નિયમોનો ઉપયોગ કરી શકીએ છીએ. કારણ કે આ નિયમ પહેલાથી પેદા કરેલ મૂલ્યના મૂલ્યનો ઉપયોગ કરે છે. તેથી અહીં કોઈપણ ભાવિ અજ્ unknownાત મૂલ્યોનો ઉપયોગ કરવાને બદલે આપણે પૂર્વ-ગણતરી કરેલ મૂલ્યોનો ઉપયોગ કરી રહ્યાં છીએ. તો હવે આપણે ફક્ત લૂપ માટે લૂ નો ઉપયોગ કરીને અને 2 * i અને 2 * i-1 એરેની સીમામાં છે કે કેમ તેની તપાસ કરીને આખી પ્રક્રિયાનું અનુકરણ કરી શકીએ છીએ. એકવાર તેની પુષ્ટિ થઈ જાય પછી, અમે એરે ભરવા માટે સૂત્રોનો ઉપયોગ કરીશું.

કોડ

જનરેટ કરેલા એરે લીટકોડ સોલ્યુશનમાં મહત્તમ મેળવો માટે સી ++ કોડ

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

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

જનરેટેડ એરે લીટકોડ સોલ્યુશનમાં મેક્સિમમ ગેટ માટે જાવા કોડ

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે આપણે બધા એન તત્વો પેદા કરીએ છીએ.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે એરે વેલ્યુ સ્ટોર કરવા માટે હંગામી એરે બનાવી છે.