သူတို့ရဲ့နံပါတ် XOR က 0 ဖြစ်ဖို့အတွက် array ရဲ့အတွဲအရေအတွက်ရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Cadence အိန္ဒိယ ကူပွန် Honeywell တကယ်ပါပဲ InfoEdge Moonfrog ဓာတ်ခွဲခန်း Pinterest
အခင်းအကျင်း bits hash ရှာဖွေခြင်း sorting

ပြXနာကသူတို့ပေးထားတဲ့ XOR ၀ န်ဆောင်မှုအတွက်အတွဲအရေအတွက်စုံကိုရှာပါ အခင်းအကျင်း of ကိန်း။ အဆိုပါပြstatementနာကြေညာချက် pair တစုံပါရှိသည်တစ်ခုခင်းကျင်းအတွက်ပစ္စုပ္ပန်အားလုံးအတွက်, အရေအတွက်ကိုရှာဖွေရန်တောင်းသည် Ai XOR Aj = 0 ။

မွတ္စု: ၁ သည်ငယ်သည်သို့မဟုတ်ညီမျှသည် i, i ထက်နည်းသည် j နှင့် j ဒီဟာက n ထက်ငယ်လား (သို့) ညီမျှသည်i < j<= n) ။

နမူနာ

သူတို့ရဲ့နံပါတ် XOR က 0 ဖြစ်ဖို့အတွက် array ရဲ့အတွဲအရေအတွက်ရှာပါ

arr[] = {2, 3, 1, 3, 2}
2

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

အညွှန်းကိန်း (0,4) နှင့် (1,3) ။

arr[] = {1, 1, 1}
3

algorithm

  1. array ထဲရှိအများဆုံး element ကိုရှာပါ။
  2. အရွယ်အစား (အများဆုံးဒြပ်စင်) တစ်ခုခင်းကျင်းပါ။
  3. i <n (အစုအဝေး၏အရှည်) ဖြစ်စဉ်တွင်ခင်းကျင်းမှုကိုဖြတ်သန်းပါ။
    1. ကျွန်ုပ်တို့ဖန်တီးထားသော array တွင် array element တစ်ခု၏ကြိမ်နှုန်းကိုရေတွက်။ သိမ်းဆည်းပါ။
  4. i <= အများဆုံးဒြပ်စင်အနေဖြင့်, count ခင်းကျင်းဖြတ်ပါ။
    1. output ကို = output ကို + count က [i] * (ရေတွက် [i] - 1) Do;
  5. ပြန်လာ output ကို / 2 ။

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

ကျနော်တို့ကိန်းတစ်ခုခင်းကျင်းရှိသည်။ အဆိုပါပြstatementနာကြေညာချက်ထိုကဲ့သို့သောခင်းကျင်းအတွက်ပစ္စုပ္ပန်စုံတွဲထွက်ရှာရန်မေးတယ် Ai XOR Aj = 0. index index ကိုသွားမည်ဖြစ်သည်။ ဆိုလိုသည်မှာကျွန်ုပ်တို့သည် array element တစ်ခု၏ကြိမ်နှုန်းကိုရေတွက်လိမ့်မည်။ ၎င်းတို့သည် count [i] * count [i-1] တွက်ချက်နိုင်ပြီး၊ output ကို။ ဒီကိုဖြေရှင်းရန်တစ်ခု အခင်းအကျင်း နှင့် array element ၏အရပျ၌ကြှနျုပျတို့၏ဒြပ်စင်ကြိမ်နှုန်းကိုသိုလှောင်မည့် count array အညွှန်းအဖြစ်ဆောင်ရွက်သောကြောင့်နံပါတ်တစ်ခုကိုသီးခြားနေရာ၌တွေ့ရှိပါက၎င်းကိုအညွှန်းအဖြစ်အသုံးပြုမည်။

ကျနော်တို့ array ထဲကအများဆုံး element ကိုတွေ့လိမ့်မည်။ အဲ့ဒီအမြင့်ဆုံး element အရွယ်အစားကိုတော့ array တစ်ခုလုပ်မယ်၊ အဲဒါက count array၊ ဒါက frequency array အဖြစ်သုံးမယ်။ ကျနော်တို့ array ကိုဖြတ်သန်းနှင့်တစ်ခုချင်းစီကို array ဒြပ်စင်၏အရေအတွက်သိုလှောင်ရန်လိုအပ်သည်။ ပြီးရင် output variable ကို 0 လို့သတ်မှတ်ပါမယ်။

ဥပမာတစ်ခုကိုသုံးသပ်ကြည့်ကြစို့။

နမူနာ

arr [] = {2, 3, 1, 3, 2} array ရဲ့အများဆုံးအရွယ်အစား 3 ဖြစ်လိမ့်မည်။

i = 0, arr [i] = 2၊ count [arr [i]] + = 1] ကိုတွက်ပါမယ်။ ဆိုလိုတာက count ရဲ့ element ရဲ့ဒုတိယအညွှန်းကိန်းက 2 တိုးလာလိမ့်မယ်။

i = 1, arr [i] = 3၊ count [arr [i]] + = 1] ကိုတွက်ပါမယ်။ ဆိုလိုတာက count ရဲ့ element ရဲ့ဒုတိယအညွှန်းကိန်းက 3 တိုးလာလိမ့်မယ်။

i = 2, arr [i] = 1, count [arr [i]] + = 1] ကိုတွက်ပါလိမ့်မည်။ ဆိုလိုသည်မှာ count element ၏ပထမအညွှန်းကိန်းသည် 1 တိုးလာလိမ့်မည်။

i = 3, arr [i] = 3၊ count [arr [i]] + = 1] ကိုတွက်ချက်လိမ့်မယ်။ count element ရဲ့တတိယအညွှန်းကိန်းက 3 တိုးလာလိမ့်မယ်။

i = 4, arr [i] = 2၊ count [arr [i]] + = 1] ကိုတွက်ပါမယ်။ ဆိုလိုတာက count ရဲ့ element ရဲ့ဒုတိယအညွှန်းကိန်းက 2 တိုးလာလိမ့်မယ်။

count က array အဖြစ် count [] = {0,1,2,2}

ဤ array ကိုကျွန်ုပ်တို့ဖြတ်သန်းသွားမည်။ output = output + count [i] * (count [i] - 1) လုပ်တိုင်းအချိန်တိုင်းတွင်ဖြစ်သည်။

ပြီးတော့ output ကို / 2 အဖြစ် output ပြန်ပေးလိမ့်မယ်။

C ++ code များက array ထဲရှိအတွဲစုံကိုရှာရန်သူတို့၏ XOR သည် 0 ဖြစ်သည်

#include<iostream>
#include<algorithm>

using namespace std;

int calculate(int a[], int n)
{
    int *maxm = max_element(a, a + 5);
    int count[*maxm + 1] = {0};

    for(int i = 0; i < n; i++)
    {
        count[a[i]] += 1;
    }
    int output = 0;
    for(int i = 0; i < (*maxm)+1; i++)
    {
        output = output + count[i] * (count[i] - 1) ;
    }
    return output/2;
}
int main()
{
    int a[] = {2, 3, 1, 3, 2};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"XOR Pairs are : "<< (calculate(a,n));
    return 0;
}
XOR Pairs are : 2

Java နံပါတ်သည်အတွဲလိုက်ရှာဖွေရန်အတွက်သူတို့၏ XOR ၀ သည် 0 ဖြစ်သည်

import java.util.Arrays;

class XORPair
{
    public static int calculate(int arr[], int n)
    {
        int max= Arrays.stream(arr).max().getAsInt();

        int count[] = new int[max+ 1];

        for (int i = 0; i < n; i++)
        {
            count[arr[i]] += 1;
        }
        int output = 0;
        for (int i = 0; i < (max) + 1; i++)
        {
            output = output + count[i] * (count[i] - 1);
        }
        return output / 2;
    }
    public static void main(String[] args)
    {
        int a[] = {2, 3, 1, 3, 2};
        int n = a.length;
        System.out.println("XOR Pairs are : "+calculate(a, n));
    }
}
XOR Pairs are : 2

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

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ O (1) Array အတွင်းရှိ element များကိုရယူရန်အချိန်လိုအပ်သည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

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

အို (မက်စ်) ဘယ်မှာမက်စ်သည် array ထဲမှာရှိတဲ့ element အားလုံးထဲမှာအများဆုံး element ဖြစ်တယ်။