એમ રેન્જ ટgગલ ઓપરેશન્સ પછી બાઈનરી એરે


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન Coursera ગોલ્ડમૅન સૅશ Google ગ્રેઓરેંજ Snapchat
અરે ક્વેરી સમસ્યા

તમને દ્વિસંગી એરે આપવામાં આવે છે, જેમાં પ્રારંભમાં 0 અને પ્રશ્નોની સંખ્યા શામેલ હોય છે. સમસ્યાનું નિવેદન મૂલ્યોને ટgleગલ કરવાનું કહે છે (0s ને 1s અને 1s ને 0s માં રૂપાંતરિત કરવું). ક્યૂ ક્વેરીઝ કર્યા પછી, પરિણામ એરે છાપો.

ઉદાહરણ

arr[] = {0, 0, 0, 0, 0}

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

સમજૂતી

1 લી ટgગલિંગ   0,1,1,1,0

2 જી ટgગલિંગ 1,0,1,1,0

3 જી ટgગલિંગ 1,0,0,0,1

એમ રેન્જ ટgગલ ઓપરેશન્સ પછી બાઈનરી એરે

અલ્ગોરિધમ

  1. એન +2 કદની બુલિયન એરે બનાવો.
  2. દરેક અનુક્રમણિકા માટે ખોટી તરીકે બુલિયન એરે પ્રારંભ કરો.
  3. હવે દરેક ક્વેરી માટે તત્વને ડાબે અને જમણે +1 પર ફ્લિપ કરો.
  4. હવે ફક્ત એરેને પ્રીફિક્સ Xor એરે તરીકે ભરો. અનુક્રમણિકા 1 થી i સુધીના તમામ તત્વોના ઝોરરને ઇન્ડેક્સ i પર સ્ટોર કરો.
  5. એરે છાપો

એમ રેન્જ ટgગલ ઓપરેશન્સ પછી બાઈનરી એરે માટે સમજૂતી

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

ટgગલિંગમાં સમાન એરેમાં શ્રેણી તરીકે આપવામાં આવેલા ચોક્કસ સ્થાનો પરના મૂલ્યોને કન્વર્ટ કરો, બધા શૂન્યોને એકમાં કન્વર્ટ કરો અને XOR ઓપરેશન કરીને તેને શૂન્યમાં ફેરવો. જો તે સમાન સંખ્યાઓ અથવા કિંમતો મળી આવે તો XOR ઓપરેશન આપણા માટે પણ એવું જ કરે છે જો તે 0 આપશે પરિણામે ખોટા અર્થ થાય છે જો તેને વિવિધ સંખ્યાનાં મૂલ્યો મળે તો. તે 1 આપશે, પરિણામે, અર્થ થાય છે સાચું. તો આપણે વેલ્યુઝને vertંધી કરવા ટ toગલિંગ ફંક્શનમાં પણ તે જ કરીશું.

એરેને પસાર કરો અને એરે પર performપરેશન કરો. વર્તમાનના અને એરેના પાછલા મૂલ્ય પર XOR ઓપરેશન કરો. જે વસ્તુ આપણે કરી હતી તેવું લાગે છે કે તે સમાન રીતે મળે છે તે આપશે 0 અન્યથા 1. આ allપરેશન બધી કિંમતોને ટgગલ કરવાની છેલ્લી હશે જે શ્રેણીમાં બનશે. અંતે, એરે છાપો.

કોડ

એમ રેન્જ ટgગલ ઓપરેશન્સ પછી બાઈનરી એરે માટે સી ++ માં અમલીકરણ

#include<iostream>

using namespace std;

void Toggle(bool arr[], int start, int end)
{
    arr[start] ^= 1;
    arr[end+1] ^= 1;
}

void getToggling(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}

void printOutput(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}

int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};

    Toggle(arr, 1, 5);
    Toggle(arr, 2, 5);
    Toggle(arr, 3, 5);

    getToggling(arr, n);

    printOutput(arr, n);
    return 0;
}
1 0 1 1 1

એમ રેન્જ ટgગલ afterપરેશંસ પછી બાઈનરી એરે માટે જાવામાં અમલીકરણ

class ToggleArray
{
    static void Toggle(boolean arr[], int start, int end)
    {
        arr[start] ^= true;
        arr[end + 1] ^= true;
    }

    static void getToggling(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            arr[k] ^= arr[k - 1];
        }
    }

    static void printOutput(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            if(arr[k] == true)
                System.out.print("1" + " ");
            else
                System.out.print("0" + " ");
        }
    }

    public static void main(String args[])
    {
        int n = 5, m = 3;
        boolean arr[] = new boolean[n + 2];

        Toggle(arr, 1, 5);
        Toggle(arr, 2, 5);
        Toggle(arr, 3, 5);

        getToggling(arr, n);

        printOutput(arr, n);
    }
}
1 0 1 1 1

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

સમય જટિલતા

ઓ (એન + ક્યૂ) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે અને “q”એ ક્વેરીઝની સંખ્યા છે. બધી પ્રશ્નો O (1) સમયમાં કરવામાં આવી રહી છે અને પછી અપડેટ માટે O (N) સમય જરૂરી છે.

અવકાશ જટિલતા

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