અપડેટ્સ વિના શ્રેણીની ક્વેરીઝ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે બ્લેકરોક જીઇ હેલ્થકેર મૂનફ્રોગ લેબ્સ સારાંશ ટેક્સી 4 સ્યુર Twilio
અરે લાર્સન અને ટુબ્રો ક્વેરી સમસ્યા

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

સમસ્યા "અપડેટ્સ વિના શ્રેણીના પ્રશ્નોની સંખ્યા" કહે છે કે તમારી પાસે એરે of પૂર્ણાંક અને એક શ્રેણી. સમસ્યાનું નિવેદન આપેલ શ્રેણીમાંના બધા તત્વોનો સરવાળો શોધવા માટે પૂછે છે.

ઉદાહરણ

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

સમજૂતી

શ્રેણી (0, 4) વચ્ચેની તમામ સંખ્યાઓનો સમાવેશ સમાવેશ થાય છે 40 અને સમાવિષ્ટ શ્રેણી (1, 3) વચ્ચેની તમામ સંખ્યાઓનો સરવાળો 24 છે.

અપડેટ્સ વિના શ્રેણીની ક્વેરીઝ

 

અલ્ગોરિધમ

  1. આપેલા એરેની જેમ કદના એરે સરવાળો બનાવો.
  2. આપેલ એરેથી પસાર થવું અને સરવાળો એરેના પાછલા તત્વનો સરવાળો અને એરેના વર્તમાન તત્વ આપ્યા અને તેને સરવાળોમાં સંગ્રહિત કરો.
  3. દરેક ક્વેરી માટે, જો ડાબી 0 ની બરાબર હોય, તો પછી સરવાળો એરે [જમણે],
  4. બાકી રકમ સરવાળો [અધિકાર] - સરવાળો [ડાબે - 1].

સમજૂતી

અમે પૂર્ણાંકની શ્રેણી અને શ્રેણી આપી છે, દરેક ક્વેરી માટે આપેલ શ્રેણીની અંદરના બધા તત્વોનો સરવાળો શોધવા માટે કહેવામાં આવ્યું છે. દરેક ક્વેરીઝમાં શ્રેણીના પ્રારંભ અને અંતિમ બિંદુ તરીકેની શ્રેણી હોય છે. આ પ્રશ્નમાં કોઈ અપડેટ ક્વેરી શામેલ નથી. તેનો અર્થ એ કે ક્વેરી જવાબ શોધતી વખતે કોઈ પણ વસ્તુને અપડેટ કરવાની જરૂર નથી. અમે ફક્ત આપેલ એરે બનાવીશું જેથી 0 અનુક્રમણિકાથી વર્તમાન સૂચકાંક સુધીના તમામ તત્વોનો સરવાળો બિલ્ટ એરેની ith સ્થિતિ પર હોય. આ રીતે, દરેક ક્વેરી ઓ (1) માં ઓ (એન) ની વધારાની જગ્યા સાથે હલ કરવામાં આવશે.

આપણે બનાવેલ સરવાળો બનાવીશું. આ અરેરેમાં, 0 થી i સુધીના તત્વોનો સરવાળો એરેરેની ith સ્થિતિ પર સંગ્રહિત કરવામાં આવશે. અમે આની ગણતરી કરીશું કારણ કે આપણે સરવાળોના અગાઉના મૂલ્ય અને આપેલા એરેનું વર્તમાન મૂલ્ય ઉમેરીશું અને તેને ટ્ર traવર્સ કરતી વખતે સરવાળાની વર્તમાન અનુક્રમણિકા સ્થિતિમાં સંગ્રહિત કરીશું. તેથી જ્યારે કોઈએ પૂછ્યું કે આ સ્થિતિ પરના તમામ નંબરોનો સરવાળો શું છે, ત્યારે આપણે ફક્ત દરેક અનન્ય એરે તત્વો માટે તે સ્થાનનું મૂલ્ય પાછું આપવાની જરૂર છે.

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

કોડ

સી ++ કોડ માટે શ્રેણી અપડેટ્સ વિના સરવાળા પ્રશ્નો

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

અપડેટ્સ વિના શ્રેણીના ક્વેરીઝ માટે જાવા કોડ

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

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

સમય જટિલતા

ઓ (એન + ક્યૂ),  કારણ કે અમને દરેક ક્વેરી માટે સરવાળાની ગણતરી કરવા O (N) ની જરૂર છે અને પછી O (1) સમય જોઈએ.

અવકાશ જટિલતા

અહીં આપેલ અભિગમમાં, આપણે 0 થી i સુધીના તત્વોનો સરવાળો સંગ્રહવા માટે એક નવી એરે સરવાળો બનાવ્યો છે. આમ આ અભિગમ જરૂરી છે ઓ (એન) જગ્યા. પરંતુ આપણે મૂળ એરેમાં પણ ફેરફાર કરી શક્યા હોત. પછી અવકાશ જટિલતા સતત ઘટાડવામાં આવી હોત.