په یو صف کې د جوړې شمیره ومومئ چې د دوی XOR 0 وي


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي کیډینس هندوستان کوپنډونیا Honeywell په حقیقت کی د معلوماتو ایجج مونفروګ لیبز پېن
پیشه بټونه هاش لټون کول ترتیب کول

ستونزه "په یو صف کې د جوړه شمیرو موندل لکه د دوی XOR 0" حالت دی چې فرض یې کړئ ، موږ یو سور of ضمیمه. د ستونزې بیان غوښتنه کوي چې په یو صف کې موجود د جوړو شمیره ومومي ، کوم چې جوړه لري Ai XOR Aj = 0.

یادونه: 1 د دې څخه لږ یا مساوي دی i, i له دې څخه کم دی j او j د n (1 <= څخه لږ یا مساوي دیi < j<= n).

بېلګه

په یو صف کې د جوړې شمیره ومومئ چې د دوی XOR 0 وي

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

تشریح

شاخص (0,4،1,3) او (XNUMX،XNUMX).

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

الګوریتم

  1. په یو صف کې موجود اعظمي عنصر ومومئ.
  2. د اندازې یو صف جوړ کړئ (اعظمي عنصر).
  3. د صف ځغلنده کړئ ، پداسې حال کې چې زه <n (د سرې اوږدوالی).
    1. په هرڅه کې چې موږ رامینځته کړي د هر یو عنصر فریکونسي حساب کړئ او خوندي کړئ.
  4. د شمېرنې صف تیر کړئ ، پداسې حال کې چې i <= اعظمي عنصر.
    1. آؤټ پ = کړئ = آؤټ ++ شمار [i] * (شمار ​​[i] - 1)؛
  5. بیرته راستنیدنه / 2.

تشریح

موږ د عدد صفونه لرو. د ستونزې بیان غوښتنه کوي چې جوړه په لین کې شتون ومومي داسې لکه چې Ai XOR Aj = 0. موږ د شاخص کولو نقشه کارول کوو ، پدې معنی چې موږ د هر صف عناصر فریکونسي حساب کوو لکه دا چې موږ یې په ګوته کولی شو که دوی کولی شي شمیرنه وکړي [i] * شمار [i-1] او په پایله کې وتنه. د دې د حل لپاره سور او په هغه ځای کې د سري عنصر کوم چې د شمېرنې سرلیکونو شاخص په توګه کار کوي په کوم کې چې موږ د خپلو عناصرو فریکونسۍ ذخیره کوو ، نو که چیرې یو شمیر په یو ځانګړي ځای کې وموندل شي ، نو موږ به دا د شاخص په توګه وکاروو.

موږ به له صف څخه اعظمي عنصر ومومو. او د دې اعظمي عنصر اندازې څخه ، موږ به یو صف جوړ کړو ، دا د سرسری شمیره ده ، دا موږ د فریکونسي صف په توګه کاروو. موږ اړتیا لرو چې د صف څخه تیر شو او د هرې عنصر شمیرې زیرمه کړو. بیا به موږ 0 ته د محصول متغیر وټاکو.

راځئ چې یوه بېلګه په نظر کې ونیسو:

بېلګه

تیر [] = {2 ، 3 ، 1 ، 3 ، 2} د صف اندازه به یې 3 وي.

i = 0 ، آرر [i] = 2 ، موږ به حساب وکړو [آر آر [i]] + = 1 ، دا پدې مانا ده چې د شمیرو عنصر دوهم شاخص به 2 لخوا زیاتوالی ومومي.

i = 1 ، آرر [i] = 3 ، موږ به حساب وکړو [آر آر [i]] + = 1 ، دا پدې مانا ده چې د شمیرو عنصر دوهم شاخص به 3 لخوا زیاتوالی ومومي.

i = 2 ، آرر [i] = 1 ، موږ به حساب وکړو [آر آر [i]] + = 1 ، دا پدې مانا ده چې د شمیرو عنصر لمړی شاخص به 1 لخوا زیاتوالی ومومي.

i = 3 ، آرر [i] = 3 ، موږ به حساب وکړو [آر آر [i]] + = 1 ، دا پدې مانا ده چې د شمیرو عنصر دریم شاخص به د 3 لخوا زیاتوالی ومومي.

i = 4 ، آرر [i] = 2 ، موږ به حساب وکړو [آر آر [i]] + = 1 ، دا پدې مانا ده چې د شمیرو عنصر دوهم شاخص به 2 لخوا زیاتوالی ومومي.

موږ د شمېرنې په څیر د سورې سرلیک لرو [] = {0,1,2,2،XNUMX،XNUMX،XNUMX}

موږ به دا صف تیر کړو ، او هر ځل چې موږ آوټ پټه = محصول + شمیره [i] * وکړو (شمیره [i] - 1).

او دا به د محصول / 2 په توګه بیرته راستانه کړي.

C ++ کوډ په صف کې د جوړې د موندلو لپاره داسې چې د دوی 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

جاوا کوډ په یو صف کې د جوړه شمیرو موندلو لپاره لکه د دوی 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) هلته "n" په صف کې د عناصرو شمیر دی. په صف کې د عناصرو لاسرسي لپاره O (1) وخت ته اړتیا ده. پدې توګه د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

او (مکس) ، چیرې چې میکس په صف کې د ټولو عناصرو ترمنځ اعظمي عنصر دی.