တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေး


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Walmart ဓာတ်ခွဲခန်းများ
အခင်းအကျင်း နည်းနည်းခြယ်လှယ် bits Bitwise-XOR

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင်ကျွန်ုပ်တို့သည် XOR Operation ကို Array အရွယ်အစားဖြင့်လုပ်ရန်လိုအပ်သည်။ ၎င်းသည် element တစ်ခုစီသည် (start + 2 * i) နှင့်တူညီပြီး i သည် element ၏ index (0-index) နှင့် start ၏တန်ဖိုးကိုဖော်ပြသောနေရာဖြစ်သည်။
ကျွန်ုပ်တို့သည် array ၏ element အားလုံး၏ bitwise XOR ကိုပြန်ရမည်။

နမူနာ

n = 4, start = 3
8

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

Array Nums သည် [3, 5, 7, 9] = (3 ^ 5 ^ 7 ^ 9) = 8 နှင့်ညီမျှသည်။
"^" bitwise XOR အော်ပရေတာနှင့်ကိုက်ညီဘယ်မှာ။

n = 1, start = 7
7

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

Array Nums များသည် [7] နှင့်ညီသည်။ ထို့ကြောင့် xor = 7 ။

ချဉ်းကပ်နည်း (Brute Force)

i = 0 to i = n-1 အတွက် loop n ကိုရိုးရှင်းစွာ run နိုင်သည်။ loop အတွက်ကျွန်ုပ်တို့သည် variable x ၌သိုလှောင်မည့်လက်ရှိ xor ဖြင့် (start + 2 * i) bitwise xor (လုပ်ခြင်း) ကိုလုပ်လိမ့်မည်။

algorithm

1. ခင်းကျင်း၏ဒြပ်စင်အညွှန်းကိန်းကိုကိုယ်စားပြုခြင်းနှင့် 0 နှင့်အတူစတငျဖို့ variable ကို ind ဖန်တီးပါ။
၂။ loop အတွက်ကာလအတွင်းလက်ရှိ xor ကိုသိမ်းဆည်းပြီး 2 နှင့်စတင်ပါ။
3. ind = n-0 မှ ind = 1 ကနေ for loop ကို run ပါ။
၄။ bit of xor ဖြင့် res ((+ + 4 * i)) နှင့်အတူ index ကိုလုပ်ပါ။ index ထဲတွင် index ကိုလုပ်ပြီး res ကိုသိမ်းပါ။
5. res ပြန်သွားပါ။

တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေးများအတွက်အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int ind=0;
    int res=0;
    for(ind=0;ind<n;ind++) res=res^(start+2*ind);

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java အစီအစဉ်

import java.lang.*;

class XorOperation
{  
    public static int xorOperation(int n, int start) 
    {

        int ind=0;
        int res=0;
        for(ind=0;ind<n;ind++) res=res^(start+2*ind);

        return res;      
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေးများအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

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

အို (N):  ဘယ်မှာ N ကိုခင်းကျင်း၏ပေးထားသောအရွယ်အစားသည်အဘယ်မှာရှိ။ N ကို element တွေအတွက် array တစ်ခုထဲမှာဖြတ်သန်းနေရတာနဲ့အမျှ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (N) ဖြစ်သည်။

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

အို (၁)  ကျွန်ုပ်တို့သည်အချို့သော variable များ မှလွဲ၍ အခြားမည်သည့်အပိုမှတ်ဉာဏ်ကိုမျှအသုံးမပြုပါ။ ထို့ကြောင့်အသုံးပြုထားသောအပိုနေရာမှာစဉ်ဆက်မပြတ်ဖြစ်သည်။

ချဉ်းကပ်မှု (နည်းနည်းခြယ်လှယ်)

အထက်ပါပြproblemနာတွင်နောက်လာမည့် element တစ်ခုစီ၏ခြားနားချက်သည် ၂ ဖြစ်သည်ကိုဆိုလိုသည်။ ဆိုလိုသည်မှာ element အားလုံးသည်ပင်ဖြစ်လိမ့်မည်သို့မဟုတ်အားလုံးသည်ထူးဆန်းမည်မဟုတ်ပါ။ ၎င်းသည်အကွာအဝေးအမျိုးမျိုးကိုဖြစ်ပေါ်စေသော်လည်းအဆက်မပြတ်ဖြစ်ပေါ်စေသည်။ ဆိုလိုသည်မှာအခြားတန်ဖိုးများရှိသည်။

နည်းနည်းခြယ်လှယ်ခြင်းအား သုံး၍ ကျွန်ုပ်တို့သည်အဆက်မပြတ်သောအချိန်များတွင်၎င်းတွင်အဆက်မပြတ်ပါဝင်သောအကွာအဝေးရှိ bitwise xor ကိုရှာနိုင်သည်။ ဘယ်လိုလုပ်ကြည့်ကြမလဲ၊ ပြီးတော့အထက်ပါပြproblemနာကိုအောက်ပါပြintoနာအဖြစ်ပြောင်းဖို့ကြိုးစားပါမယ်။

အကွာအဝေး = [3,4,5,6,7,8,9,10] ဆိုပါစို့၊ ပထမနှင့်နောက်ဆုံးဒြပ်စင်အကြားအကွာအဝေးတွင် xor ကိုအသုံးပြုရမည်။

x ကဘာကိန်းတူမလဲ၊ y က xie y = x + 1 ရဲ့နံပါတ်ပါ။ x နှင့် y ၏ xor သည်အမြဲတမ်းဖြစ်လိမ့်မည်ကိုအလွယ်တကူခွဲခြမ်းစိတ်ဖြာနိုင်သည်။ (သို့မဟုတ်) နံပါတ်တစ်ခုစီ၏ xor နှင့်အနီးရှိမကိန်းများသည် ၁ ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ပထမနှင့်နောက်ဆုံးနံပါတ်များအကြားပင်မကိန်းအားလုံးသည် xor ကိုညီမျှသည်ဟုဆိုနိုင်သည်။ ၁ ။
i.e.   4^5=1,  6^7=1,  8^9=1

ဒီစုံတွဲအရေအတွက်ကမကိန်းဆိုလျှင် 1st even နံပါတ်နှင့်နောက်ဆုံးမကိန်းအကြားရှိ xor က 1 ဖြစ်မယ်။
ဆိုလိုသည်မှာ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 = 1 ^ 1 ^ 1 = 1

ယခုကျွန်ုပ်တို့သည် 3 နှင့် 10 ဖြစ်သောအဆုံးရာထူးများတွင်နံပါတ်များကိုသာကျန်တော့သည်။ ထို့ကြောင့်အောက်ပါပုံတွင်ပြထားသည့်အတိုင်းကျွန်ုပ်တို့၏ဖြေဆိုချက်သည် ၃ ^ ၁ ^ ၁၀ = ၈ ဖြစ်သည်။

တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေး

ပြtheနာကိုဆက်တိုက် XOR အဖြစ်ပြောင်းခြင်း

အထက်ပါပြproblemနာတွင်ကျွန်ုပ်တို့သည် element တစ်ခုစီအကြားရှိအကွာအဝေးကို ၂ မှ ၁ အထိလျှော့ချနိုင်သည် bitwise ညာဘက်ပြောင်းကုန်ပြီ ဒြပ်စင်တစ်ခုချင်းစီကို (၂ ဖြင့်စားခြင်းနှင့်အတူတူ) ။ ဒီလိုလုပ်ခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်နောက်ဆုံးသောအစိတ်အပိုင်းများကိုသာထိခိုက်သည်။ ဒါကြောင့်ငါတို့ရဲ့ ans ၏နောက်ဆုံး bit ကိုအောက်ပါအတိုင်းသိမ်းဆည်းပါ။

1. Array မှာရှိတဲ့ element အားလုံးဟာထူးဆန်းနေပြီး element အားလုံးရဲ့စုစုပေါင်းလည်းမကိန်းဖြစ်ခဲ့ရင် lastbit = 1 ။
2. Else lastbit = 0 ။

အခု element တစ်ခုချင်းစီကိုညာဘက်ရွှေ့ပြီးတဲ့အခါကျွန်တော်တို့ရဲ့ range က

start / 2 start / 2 +1 စတင်၊ 2 + 2 စတင်ပါ။ ။ ။ ။ , စတင် / 2 + (--1) ။

ဘယ်မှာပထမ ဦး ဆုံး = start / 2 နှင့်နောက်ဆုံး = start / 2 + (n-1) ။

ယခုကျွန်ုပ်တို့သည်အကွာအဝေးရှိ xor အဆုံးဒြပ်စင်များ၏ bitwise xor နှင့်အားလုံး - ပင်မကိန်းအတွဲများကိုရှာဖွေခြင်းဖြင့်အလွယ်တကူရှာဖွေနိုင်သည်။

xor ရှာတွေ့ပြီးနောက်ငါတို့ရှိသည် လက်ဝဲပြောင်းကုန်ပြီ bitwise ကျွန်ုပ်တို့၏နောက်ဆုံးအဖြေတွင် bits ၏မူလအနေအထားကိုရရှိရန် 1 မှရလဒ်။ နောက်ဆုံးအနေဖြင့် lastbit ကိုရလဒ်သို့ထပ်ထည့်ပါ။

တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေးများအတွက်အကောင်အထည်ဖော်မှု

C ++ အစီအစဉ်

#include <bits/stdc++.h>
using namespace std;

int xorOperation(int n, int start) {

    int lastbit;
    if(n%2==1  &&  start%2==1) lastbit=1;
    else lastbit=0;

    //after 1 right shift
    int first= start/2;
    int last= start/2+ n-1;

    int res=0;

    if(first%2==1)
    { 
        res^=first; 
        first++;
    }

    if(last%2==0)
    {
        res^=last;
        last--;
    }


    int pairs=0;            //in between pairs
    if(first<last)   pairs= (last-first+1)/2;    
    if(pairs%2==1) res^=1;   

    res<<=1;                // back to 1 left shift
    res+=lastbit;           // attaching last bit

    return res;

}
int main() 
{
        int n=4;
        int start=3;
    cout<<xorOperation(n,start)<<endl;

  return 0; 
}
8

Java အစီအစဉ်

import java.lang.*;

class Rextester
{  
    public static int xorOperation(int n, int start) 
    {

        int lastbit;
        if(n%2==1  &&  start%2==1) lastbit=1;
        else lastbit=0;

        //after 1 right shift
        int first= start/2;
        int last= start/2+ n-1;

        int res=0;

        if(first%2==1)
        { 
            res^=first; 
            first++;
        }

        if(last%2==0)
        {
            res^=last;
            last--;
        }


        int pairs=0;            //in between pairs
        if(first<last)   pairs= (last-first+1)/2;    
        if(pairs%2==1) res^=1;   

        res<<=1;                // back to 1 left shift
        res+=lastbit;           // attaching last bit

        return res;     
    }
    
    
    public static void main(String args[])
    {
        int n=4;
        int start=3;

        System.out.println(xorOperation(n,start));
        
    }
}
8

တစ်ခု Array Leetcode ဖြေရှင်းချက်အတွက် XOR စစ်ဆင်ရေးများအတွက်ရှုပ်ထွေးအားသုံးသပ်ခြင်း

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

အို (၁)  ကျွန်ုပ်တို့သည် array ၏အစိတ်အပိုင်းများအားလုံးကိုဖြတ်သန်းသွားခြင်းမဟုတ်ပါကနည်းနည်းခြယ်လှယ်ခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်၎င်းကိုစဉ်ဆက်မပြတ်ပြုလုပ်ခဲ့သည်။

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

အို (၁)  ဤတွင်လည်းအသုံးပြုသောအပိုမှတ်ဉာဏ်စဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။