M အကွာအဝေးပြီးနောက် Binary ခင်းကျင်းစစ်ဆင်ရေး toggle


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Coursera Goldman Sachs Google GreyOrange Snapchat
အခင်းအကျင်း ပြeryနာပြ.နာ

binary array ကိုပေးတယ်။ သူက ၀ မှာကန ဦး ၀ နဲ့ query တွေအတွက်ပါ အဆိုပါပြstatementနာကြေညာချက် (0s 0s သို့ 1s သို့ 1s သို့ပြောင်းလဲ) တန်ဖိုးများကို toggle ရန်မေးတယ်။ Q မေးမြန်းချက်များလုပ်ဆောင်ပြီးနောက်ရလဒ်ထွက်ခင်းကျင်းမှုကိုပုံနှိပ်ပါ

နမူနာ

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

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

ရှင်းလင်းချက်

1st toggling   0,1,1,1,0

2nd toggling 1,0,1,1,0

3rd toggling 1,0,0,0,1

M အကွာအဝေးပြီးနောက် Binary ခင်းကျင်းစစ်ဆင်ရေး toggle

algorithm

  1. n + 2 အရွယ် Boolean ခင်းကျင်းပါ။
  2. အညွှန်းတစ်ခုချင်းစီအတွက် false အဖြစ် boolean ခင်းကျင်းမှုကိုအစပြုပါ။
  3. အခုဆိုရင် query တစ်ခုချင်းစီအတွက် element ကို left နှင့် right + 1 index မှာလှန်လိုက်ပါ။
  4. ယခု array ကို prefix xor array အဖြစ်ဖြည့်ပါ။ element တွေရဲ့ xor ကို index1 ကနေ i အထိ index မှာသိမ်းထားပါ။
  5. ခင်းကျင်းပုံနှိပ်ပါ

M အကွာအဝေးကိုစစ်ဆင်ရေး toggle ပြီးနောက် Binary ခင်းကျင်းများအတွက်ရှင်းပြချက်

တစ် ဦး binary ပေးထားသည် အခင်းအကျင်း0s နှင့် 1s များပါဝင်ပြီးနာမကအကြံပြုထားသည်။ ဒါပေမယ့်ကန ဦး မှာ၊ 0s အဖြစ်သာတန်ဖိုးများပါရှိသည်။ မေးမြန်းမှု၏နံပါတ်အရေအတွက်ကိုပေးထားသည်။ မေးမြန်းချက်တစ်ခုစီတွင်တန်ဖိုးနှစ်မျိုးပါ ၀ င်သည်။ တန်ဖိုးများသည်အကွာအဝေး၏အစနှင့်အကွာအဝေး၏အဆုံးသတ်အမှတ်ဖြစ်သည်။ ဤအကွာအဝေးအတွင်းကျွန်ုပ်တို့သည် toggling ကိုဆိုလိုသည်။ ကျွန်ုပ်တို့သည် 0s များကို 1s နှင့် 1s သို့ 0s Q နံပါတ်သို့ပြောင်းလဲရန်လိုသည်။ ကြိမ်၏မေးမြန်းမှုနံပါတ်) ။ ဒီအတွက်ကျနော်တို့ a ကိုလုပ်မယ် Boolean n + 2 ခင်းကျင်းမှု၏အကျယ် ၂ ခုထက်ပိုသော array ။ ထိုအခါကျွန်ုပ်တို့သည်တန်ဖိုးများ Q ၏အကြိမ်အရေအတွက်ကိုပြောင်းလဲသွားမည်။ အကယ်၍ ကျွန်ုပ်တို့တွင်မေးမြန်းချက်များစွာရှိပါက၎င်းကိုမိမိကိုယ်ကိုခေါ်ဆိုစရာမလိုတော့ဘဲ၊ ၎င်းကိုကွင်းဆက်တစ်ခုပြုလုပ်ပြီးမတူညီသောစုံစမ်းမှုနံပါတ်များနှင့်ထည့်သွင်းမှုများပြုလုပ်လိမ့်မည်။

toggling တွင်တန်ဖိုးများကိုအတူတူပင်ခင်းကျင်းတစ်ခုအတွင်းရှိအကွာအဝေးတစ်ခုအနေဖြင့်သတ်မှတ်သည်။ သုညများအားလုံးကိုသုညသို့ပြောင်းပေးသည် XOR ကိုလုပ်ဆောင်ခြင်းအားဖြင့်သုညသို့ပြောင်းသည်။ အကယ်၍ ၎င်းသည်တူညီသောနံပါတ်များသို့မဟုတ်တန်ဖိုးများကိုတွေ့ရှိပါကတန်ဖိုးမတူညီသောအရေအတွက်ကိုတွေ့ရှိပါက false ဟုအဓိပ္ပာယ်တူသော 0 ကိုပေးပါလိမ့်မည်။ ဒါက ၁ ကိုပေးလိမ့်မယ်။ ဒီတော့ toggling function ထဲမှာလည်းအလားတူပဲတန်ဖိုးတွေကို invert လုပ်ပါမယ်။

Array ကိုဖြတ်ပြီးစစ်ဆင်ရေးကိုလုပ်ဆောင်ပါ။ လက်ရှိနှင့်ခင်းကျင်း၏ယခင်တန်ဖိုးအပေါ် XOR စစ်ဆင်ရေးလုပ်ဆောင်ပါ။ နည်းနည်းချင်းတွေ့ရင် 0 ရလိမ့်မယ်။ ဒီစစ်ဆင်ရေးဟာအကွာအဝေးအတွင်းဖြစ်လာမယ့်တန်ဖိုးတွေအားလုံးကိုနောက်ဆုံးပြောင်းလိမ့်မယ်။ နောက်ဆုံးအနေနဲ့ခင်းကျင်းပုံနှိပ်ပါ။

ကုဒ်

M အကွာအဝေး toggle စစ်ဆင်ရေးပြီးနောက် Binary ခင်းကျင်းဘို့ C ++ အတွက်အကောင်အထည်ဖော်မှု

#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

M အကွာအဝေး toggle စစ်ဆင်ရေးပြီးနောက် Binary array အတွက် Java တွင်အကောင်အထည်ဖော်ခြင်း

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n + q) ဘယ်မှာ “ n” သည် array ထဲမှ element အရေအတွက်နှင့်q"မေးမြန်းချက်များ၏နံပါတ်ဖြစ်ပါတယ်။ မေးမြန်းချက်အားလုံးကိုအို (၁) အချိန်တွင်လုပ်ဆောင်ပြီး၊ နောက်ဆုံး (အို) အချိန်လိုအပ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။