ప్రశ్నల తరువాత సంఖ్యల మొత్తం  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది నిజానికి
అల్గోరిథంలు అర్రే కోడింగ్ ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions

సమస్యల నివేదిక  

ఈ సమస్యలో, మాకు ఒక ఇవ్వబడుతుంది అమరిక శ్రేణుల పూర్ణాంకం మరియు శ్రేణి ప్రశ్నలు. కొరకు imp ప్రశ్న, మనకు రెండు పారామితులు ఉంటాయి, ఇండెక్స్ మరియు Val. ప్రతి ప్రశ్న తరువాత, మేము జోడిస్తాము Val శ్రేణికి [సూచిక]. మేము మొత్తం మొత్తాన్ని కనుగొనాలి కూడా ప్రతి ప్రశ్న తర్వాత శ్రేణిలోని పూర్ణాంకాలు మరియు పూర్ణాంకాల వెక్టర్‌గా తిరిగి ఇవ్వండి.

ఉదాహరణ

A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
8 6 2 4
A = [1,2,3,4], queries = [[2,0],[-2,2],[6,0],[4,2]]
6 6 6 6

అప్రోచ్  

ప్రశ్నల తరువాత సమాన సంఖ్యల మొత్తాన్ని అమలు చేయడం

ఒక ప్రాథమిక విధానం:

ప్రతి ప్రశ్నకు, సంబంధిత మూలకాన్ని నవీకరించండి, ఆపై మొత్తం సంఖ్యల మొత్తాన్ని కనుగొనడానికి మొత్తం శ్రేణి ద్వారా ప్రయాణించండి. కానీ, ఈ విధానం మొత్తం ప్రశ్నకు O (N * Q) కు దారితీసే ప్రతి ప్రశ్నకు O (N) సమయం పడుతుంది.

A ని నిర్వహించడం ద్వారా మనం బాగా చేయగలం ప్రీ మొత్తం ఇది శ్రేణిలోని అన్ని సమాన సంఖ్యల మొత్తం. ప్రతి ప్రశ్నకు, దాని సూచికలోని మూలకం దీనికి దోహదం చేస్తుందో లేదో మనం తనిఖీ చేయవచ్చు కూడా మొత్తం ముందుగా లెక్కించబడుతుంది (A [సూచిక]% 2 == 0 అని తనిఖీ చేయడం ద్వారా). అవును అయితే, మేము దానిని నడుస్తున్న మొత్తం నుండి తీసివేసి, A [సూచిక] ను A [సూచిక] + val గా నవీకరిస్తాము. ఆ తరువాత, A [సూచిక] సమానంగా ఉందో లేదో మనం మళ్ళీ తనిఖీ చేయాలి. అవును అయితే, మేము దీనికి జోడిస్తాము కూడా_సమ్. మిగతా అన్ని అంశాలు కూడా ప్రభావితం కానందున ఇది ఆ ప్రశ్నకు సమాధానం అవుతుంది. అందువల్ల, మేము ప్రతి ప్రశ్నకు O (1) సమయంలో సమాధానం ఇస్తాము.

ఇది కూడ చూడు
డీకంప్రెస్ రన్-లెంగ్త్ ఎన్కోడ్ లిస్ట్ లీట్కోడ్ సొల్యూషన్

సి ++ ప్రోగ్రామ్

#include <bits/stdc++.h>

using namespace std;

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
    int evenSum = 0;

    for(int &x : A) {
        if(x % 2 == 0) {
            evenSum += x;
        }
    }

    int n = queries.size() , val , idx;
    vector <int> ans(n);
    for(int i = 0 ; i < n ; i++) {
        val = queries[i][0] , idx = queries[i][1];
        if(A[idx] % 2 == 0) evenSum -= A[idx];
        A[idx] += val;
        if(A[idx] % 2 == 0) evenSum += A[idx];
        ans[i] = evenSum;
    }

    return ans;
}

int main() {
    vector <int> A = {1 , 2 , 3 , 4};
    vector < vector <int> > queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
    vector <int> ans = sumEvenAfterQueries(A , queries);
    for(int &x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

జావా ప్రోగ్రామ్

class sum_even_after_queries {
    public static void main(String args[]) {
        int[] A = {1 , 2 , 3 , 4};
        int[][] queries = {{1 , 0} , {-3 , 1} , {-4 , 0} , {2 , 3}};
        int[] ans = sumEvenAfterQueries(A , queries);
        for(int x : ans)
            System.out.print(x + " ");
        System.out.println();
    }

    public static int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int evenSum = 0;

        for(int x : A) {
            if(x % 2 == 0) {
                evenSum += x;
            }
        }
        int n = queries.length , val , idx;
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++) {
            val = queries[i][0];
            idx = queries[i][1];

            if(A[idx] % 2 == 0) evenSum -= A[idx];
            A[idx] += val;
            if(A[idx] % 2 == 0) evenSum += A[idx];
            ans[i] = evenSum;
        }

        return ans;
    }
}
8 6 2 4

ప్రశ్నల తరువాత సమాన సంఖ్యల సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N + Q), ఇక్కడ, ఇచ్చిన శ్రేణి యొక్క N = పరిమాణం. Q = ప్రశ్నల సంఖ్య. మేము కనుగొనడానికి O (N) సమయాన్ని వెచ్చిస్తాము కూడా మొత్తం మరియు ప్రతి ప్రశ్నకు సమాధానం ఇవ్వడానికి O (Q) సమయం.

అంతరిక్ష సంక్లిష్టత 

O (1), మేము స్థిరమైన మెమరీ స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.