બહુવિધ એરે રેન્જ વૃદ્ધિ કામગીરી પછી સુધારેલા એરે છાપો  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એક્સપેડિયા ફ્રીચાર્જ Google ખરેખર મૂનફ્રોગ લેબ્સ ઓલા કેબ્સ ક્વોલિટિક્સ
અરે ક્વેરી સમસ્યા

સમસ્યા "મલ્ટિપલ એરે રેન્જ ઇન્ક્રીમેન્ટ ઓપરેશન્સ પછી મોડીફાઇડ એરે છાપો" કહે છે કે તમને એ પૂર્ણાંક એરે અને 'ક્વિ' નંબરની ક્વેરીઝ આપવામાં આવી છે. એક પૂર્ણાંક મૂલ્ય "d" પણ આપવામાં આવે છે. દરેક ક્વેરીમાં બે પૂર્ણાંકો હોય છે, પ્રારંભિક મૂલ્ય અને અંતિમ મૂલ્ય. સમસ્યા નિવેદન આપેલ શ્રેણીની અંદર એરેમાંના તમામ મૂલ્યો "ડી" દ્વારા વધારવા માટે પૂછે છે. સંશોધિત એરે છાપો.

ઉદાહરણ  

arr[] = {2, 5, 1, 4, 7, 9}
Query: (1, 2), (3, 5), (4, 5), (2, 4), (1, 3)
d = 2
2 9 7 10 13 13

સમજૂતી

અનુક્રમણિકા (1,2) માંથી વૃદ્ધિ પછી r 2, 7, 3, 4, 7, 9 {થશે

હવે અનુક્રમણિકા (3,5,)) થી વૃદ્ધિ {૨,,,,,,,,, ૧} થશે

અનુક્રમણિકામાંથી ફરીથી વધારો (4,5) એઆર {2, 7, 3, 6, 11, 13 be થશે

હવે અનુક્રમણિકા (2,4,)) થી વૃદ્ધિ {૨,,,,,,,,, ૧} થશે

અનુક્રમણિકામાંથી ફરીથી વધારો (1,3) એઆર {2, 9, 7, 10, 13, 13 be થશે

 

બહુવિધ એરે રેન્જ વૃદ્ધિ કામગીરી પછી સુધારેલા એરે છાપોપિન

બહુવિધ એરે રેન્જ વૃદ્ધિ ક્રિયાઓ માટે અલ્ગોરિધમ  

  1. આપેલા એરેના સમાન કદના એરેને ઘોષણા કરો.
  2. પ્રશ્નોની કુલ સંખ્યા 0 થી એરેને વટાવી દો.
  3. આપેલ શ્રેણીમાં આપણે બનાવેલા એરેમાં આપેલ મૂલ્ય ઉમેરો. આપેલ ક્વેરીની અંતિમ શ્રેણી એરેની લંબાઈ કરતા ઓછી છે કે કેમ તે તપાસો. જો સાચું હોય, તો આપણે બનાવેલા એરેમાંથી "ડી" ની કિંમત ઘટાડો.
  4. આપેલ એરેને પસાર કરો અને વર્તમાન અને પાછલા મૂલ્યો અને આપેલા એરેના ઉમેરા સાથે આઉટપુટ એરેને અપડેટ કરો.
  5. અપડેટ થયેલ એરે છાપો.
આ પણ જુઓ
એમ દ્વારા વિભાજ્ય રકમ સાથે સબસેટ

સમજૂતી

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

હવે આપણે ક્વેરીઝની સંખ્યા સુધી લૂપ ચલાવીએ છીએ. આપેલ વેલ્યુના ઉમેરા સાથે આઉટપુટ એરેને અપડેટ કરીશું d, ક્વેરીના પ્રારંભિક અનુક્રમણિકા પર. તપાસો કે ક્વેરીનું અંતિમ મૂલ્ય એરેની લંબાઈ કરતા ઓછું છે કે નહીં. જો તે સાચું હોય તો સાચા હોવાનું જણાય તો આઉટપુટ એરેમાં અગાઉના અપડેટ કરેલ વેલ્યુથી ડી ઘટાડો. આ સુનિશ્ચિત કરવા માટે છે કે આપણે શ્રેણી અને મૂલ્યોથી બહાર જઈશું નહીં.

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

આ પણ જુઓ
તમામ નકારાત્મક નંબર્સને શરૂઆત અને હકારાત્મક વધારાની જગ્યા સાથે સમાપ્ત કરવા માટે હકારાત્મક સ્થાનાંતરિત કરો

કોડ  

મલ્ટિપલ એરે રેન્જ ઇન્ક્રીમેન્ટ ઓપરેશન્સ પછી સુધારેલા એરે છાપવા માટે સી ++ કોડ

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

struct query
{
    int start, end;
};

void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
    int sum[n];
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; i++)
    {
        sum[q_arr[i].start] += d;

        if ((q_arr[i].end + 1) < n)
            sum[q_arr[i].end + 1] -= d;
    }
    arr[0] += sum[0];
    for (int i = 1; i < n; i++)
    {
        sum[i] += sum[i - 1];
        arr[i] += sum[i];
    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {2, 5, 1, 4, 7, 9};
    struct query q_arr[] = { { 1, 2 }, { 3, 5 },  {4,5 },
        { 2, 4 }, { 1, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q_arr) / sizeof(q_arr[0]);

    int d = 2;

    cout << "Original Array:\n";
    printArray(arr, n);

    incrementByD(arr, q_arr, n, m, d);

    cout << "\nModified Array:\n";
    printArray(arr, n);

    return 0;
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

બહુવિધ એરે રેન્જ વૃદ્ધિ કામગીરી પછી સુધારેલા એરે છાપવા માટે જાવા કોડ

class modifiedArray
{
    static class query
    {
        int start, end;

        query(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

    public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
    {
        int[] sum = new int[n];

        for (int i = 0; i < m; i++)
        {
            sum[q_arr[i].start] += d;

            if ((q_arr[i].end + 1) < n)
                sum[q_arr[i].end + 1] -= d;
        }
        arr[0] += sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] += sum[i - 1];
            arr[i] += sum[i];
        }
    }

    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    public static void main(String[] args)
    {
        int[] arr = { 2, 5, 1, 4, 7, 9};
        query[] q_arr = {new query(1, 2),new query(3,5),new query(4, 5),
                  new query(2, 4),new query(1, 3)
        };

        int n = arr.length;
        int m = q_arr.length;
        int d = 2;
        System.out.println("Original Array:");
        printArray(arr, n);

        incrementByD(arr, q_arr, n, m, d);
        System.out.println("\nModified Array:");
        printArray(arr, n);
    }
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

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

સમય જટિલતા

 ઓ (ક્યૂ + એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે અને “ક્યૂ ” પ્રશ્નોની સંખ્યા છે. આપણે ઉપસર્ગ રકમની જેમ અભિગમનો ઉપયોગ કર્યો હોવાથી, આપણી પાસે રેખીય સમયની જટિલતા છે.

આ પણ જુઓ
સિક્કો ચેન્જ સમસ્યા

અવકાશ જટિલતા

 ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.