എം ശ്രേണി ടോഗിൾ പ്രവർത്തനങ്ങൾക്ക് ശേഷമുള്ള ബൈനറി അറേ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ Coursera ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ ഗ്രേ ഓറഞ്ച് Snapchat
അറേ അന്വേഷണ പ്രശ്നം

നിങ്ങൾക്ക് ഒരു ബൈനറി അറേ നൽകിയിട്ടുണ്ട്, അതിൽ തുടക്കത്തിൽ 0 ഉം ചോദ്യങ്ങളുടെ Q എണ്ണവും അടങ്ങിയിരിക്കുന്നു. പ്രശ്‌ന പ്രസ്താവന മൂല്യങ്ങൾ ടോഗിൾ ചെയ്യാൻ ആവശ്യപ്പെടുന്നു (0 സെ 1 സെ, 1 സെ 0 സെ ആക്കി മാറ്റുന്നു). Q ചോദ്യങ്ങൾ നടത്തിയ ശേഷം, ഫലമായ അറേ പ്രിന്റുചെയ്യുക.

ഉദാഹരണം

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

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

വിശദീകരണം

ആദ്യ ടോഗിംഗ്   0,1,1,1,0

രണ്ടാമത്തെ ടോഗിംഗ് 1,0,1,1,0

മൂന്നാമത്തെ ടോഗിംഗ് 1,0,0,0,1

എം ശ്രേണി ടോഗിൾ പ്രവർത്തനങ്ങൾക്ക് ശേഷമുള്ള ബൈനറി അറേ

അൽഗോരിതം

  1. ഒരു n + 2 വലുപ്പത്തിലുള്ള ബൂളിയൻ അറേ സൃഷ്ടിക്കുക.
  2. ഓരോ സൂചികയ്ക്കും ബൂലിയൻ അറേ തെറ്റാണെന്ന് സമാരംഭിക്കുക.
  3. ഇപ്പോൾ ഓരോ ചോദ്യത്തിനും ഇടത്, വലത് + 1 സൂചികയിലെ ഘടകം ഫ്ലിപ്പുചെയ്യുക.
  4. ഇപ്പോൾ അറേ പ്രിഫിക്‌സ് xor അറേ ആയി പൂരിപ്പിക്കുക. സൂചിക 1 മുതൽ i വരെയുള്ള എല്ലാ ഘടകങ്ങളുടെയും xor സൂചിക i ൽ സംഭരിക്കുക.
  5. അറേ പ്രിന്റുചെയ്യുക

ഓം ശ്രേണി ടോഗിൾ പ്രവർത്തനങ്ങൾക്ക് ശേഷം ബൈനറി അറേയ്ക്കുള്ള വിശദീകരണം

ഒരു ബൈനറി നൽകി ശ്രേണി, ഇത് 0 സെ, 1 സെ എന്നിവ ഉൾക്കൊള്ളുന്നു, പേര് സൂചിപ്പിക്കുന്നത് പോലെ. എന്നാൽ തുടക്കത്തിൽ, അതിൽ 0 സെ ആയി മൂല്യങ്ങൾ മാത്രമേ അടങ്ങിയിട്ടുള്ളൂ. ചോദ്യങ്ങളുടെ Q നമ്പർ നൽകി. ഓരോ ചോദ്യത്തിലും രണ്ട് മൂല്യങ്ങളുണ്ട്, മൂല്യങ്ങൾ ഒരു ശ്രേണിയുടെ ആരംഭ പോയിന്റും ഒരു ശ്രേണിയുടെ അവസാന പോയിന്റുമാണ്, ഈ ശ്രേണികൾക്കുള്ളിൽ, ടോഗിൾ ചെയ്യുന്ന മൂല്യങ്ങൾ ടോഗിൾ ചെയ്യണം, അതായത് ടോഗിംഗ് എന്നാൽ 0 സെ 1 സെ, 1 സെ 0 സെ ക്യു നമ്പറായി പരിവർത്തനം ചെയ്യണം ( ചോദ്യ നമ്പർ) തവണ. ഇതിനായി, ഞങ്ങൾ ഒരു സൃഷ്ടിക്കാൻ പോകുന്നു ബൂളിയൻ അറേ, വലുപ്പം രണ്ട് + അറേയുടെ നീളം n + 2. അപ്പോൾ നമ്മൾ മൂല്യങ്ങളുടെ Q എണ്ണം ടോഗിൾ ചെയ്യാൻ പോകുന്നു, ഞങ്ങൾക്ക് കൂടുതൽ ചോദ്യങ്ങൾ ഉണ്ടെങ്കിൽ, അതിനെ ഞങ്ങൾ സ്വയം വിളിക്കേണ്ടതില്ല, പകരം, ഞങ്ങൾ ഒരു ലൂപ്പ് ഉണ്ടാക്കി വ്യത്യസ്ത അന്വേഷണ നമ്പറും ഇൻപുട്ടുകളും ഉപയോഗിച്ച് വിളിക്കും.

ടോഗിളിംഗിൽ, ഒരേ ശ്രേണിയിലെ ഒരു ശ്രേണിയായി നൽകിയിരിക്കുന്ന കൃത്യമായ സ്ഥലങ്ങളിലെ മൂല്യങ്ങൾ പരിവർത്തനം ചെയ്യുക, എല്ലാ പൂജ്യങ്ങളെയും ഒന്നായി പരിവർത്തനം ചെയ്യുക, കൂടാതെ XOR പ്രവർത്തനം നടത്തി പൂജ്യമായി മാറ്റുക. ഒരേ സംഖ്യകളോ മൂല്യങ്ങളോ കണ്ടെത്തിയാൽ XOR പ്രവർത്തനം ഞങ്ങൾക്ക് ഇത് ചെയ്യും, അത് 0 നൽകും, ഫലമായി മറ്റൊരു മൂല്യങ്ങൾ കണ്ടെത്തിയാൽ അത് തെറ്റാണ്. ഇത് 1 നൽകും, അതിന്റെ ഫലമായി ശരി എന്നാണ് അർത്ഥമാക്കുന്നത്. അതിനാൽ മൂല്യങ്ങൾ വിപരീതമാക്കാനായി ടോഗിംഗ് ഫംഗ്ഷനിലും ഞങ്ങൾ ഇത് ചെയ്യും.

അറേയിലൂടെ സഞ്ചരിച്ച് അറേയിൽ പ്രവർത്തനം നടത്തുക. അറേയുടെ നിലവിലുള്ളതും മുമ്പത്തെ മൂല്യത്തിലും XOR പ്രവർത്തനം നടത്തുക. അതേ ബിറ്റ് കണ്ടെത്തുന്നതുപോലെ ഞങ്ങൾ ചെയ്ത കാര്യം അത് 0 അല്ലാത്തപക്ഷം നൽകും 1. ഒരു പരിധിക്കുള്ളിൽ മാറുന്ന എല്ലാ മൂല്യങ്ങളും ടോഗിൾ ചെയ്യുന്ന അവസാനത്തേതായിരിക്കും ഈ പ്രവർത്തനം. അവസാനമായി, അറേ പ്രിന്റുചെയ്യുക.

കോഡ്

എം ശ്രേണി ടോഗിൾ പ്രവർത്തനങ്ങൾക്ക് ശേഷം ബൈനറി അറേയ്‌ക്കായി സി ++ ൽ നടപ്പിലാക്കൽ

#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

എം ശ്രേണി ടോഗിൾ പ്രവർത്തനങ്ങൾക്ക് ശേഷം ബൈനറി അറേയ്‌ക്കായി ജാവയിൽ നടപ്പിലാക്കൽ

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n + q) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം കൂടാതെ “q”എന്നത് ചോദ്യങ്ങളുടെ എണ്ണം. എല്ലാ ചോദ്യങ്ങളും O (1) സമയത്തിലാണ് നടപ്പിലാക്കുന്നത്, തുടർന്ന് അപ്‌ഡേറ്റിന് O (N) സമയം ആവശ്യമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.