تعداد جفتهایی را در یک آرایه پیدا کنید که XOR آنها 0 باشد


سطح دشواری متوسط
اغلب در کادنس هند کوپن دونیا شرکت Honeywell در واقع InfoEdge آزمایشگاه Moonfrog پینترست
صف بیت مخلوط جستجو مرتب سازی

مسئله "پیدا کردن تعداد جفتها در یک آرایه به گونه ای که 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. آرایه شمارش را رد کنید ، در حالی که من <= حداکثر عنصر است.
    1. خروجی انجام دهید = خروجی + تعداد [i] * (تعداد [i] - 1) ؛
  5. خروجی برگشتی / 2.

توضیح

ما یک آرایه از اعداد صحیح داریم. بیانیه مسئله می خواهد جفت موجود در آرایه ای را کشف کند به گونه ای که Ai XOR Aj = 0. ما می خواهیم از نقشه برداری شاخص استفاده کنیم ، به این معنی که ما می خواهیم فرکانس هر عنصر آرایه را بشماریم به طوری که اگر آنها بتوانند [i] * count [i-1] را حساب کنند و در نتیجه خروجی برای حل این استفاده کنید صف و در آن مکان از عنصر آرایه که به عنوان شاخصی از آرایه شمارش که در آن می خواهیم فرکانس عناصر خود را ذخیره کنیم ، عمل می کند ، بنابراین اگر یک عدد در یک مکان خاص پیدا شود ، ما می خواهیم از آن به عنوان شاخص استفاده کنیم.

ما حداکثر عنصر را از آرایه پیدا خواهیم کرد. و از حداکثر اندازه عنصر ، ما می خواهیم یک آرایه درست کنیم ، این آرایه count است ، ما می خواهیم از آن به عنوان یک آرایه فرکانسی استفاده کنیم. ما باید آرایه را رد کنیم و تعداد هر عنصر آرایه را ذخیره کنیم. سپس متغیر خروجی را روی 0 قرار می دهیم.

اجازه بدین مثالی را مطرح کنیم:

مثال

arr [] = {2 ، 3 ، 1 ، 3 ، 2} حداکثر اندازه آرایه 3 خواهد بود.

i = 0 ، arr [i] = 2 ، ما شمارش [arr [i]] + = 1 را انجام خواهیم داد ، به این معنی که شاخص 2 عنصر شمارش 1 افزایش می یابد.

i = 1 ، arr [i] = 3 ، ما شمارش [arr [i]] + = 1 را انجام خواهیم داد ، به این معنی که شاخص 3 عنصر شمارش 1 افزایش می یابد.

i = 2 ، arr [i] = 1 ، ما شمارش [arr [i]] + = 1 را انجام خواهیم داد ، به این معنی که شاخص اول عنصر شمارش 1 افزایش می یابد.

i = 3 ، arr [i] = 3 ، ما شمارش [arr [i]] + = 1 را انجام خواهیم داد ، به این معنی که شاخص 3 عنصر شمارش 1 افزایش می یابد.

i = 4 ، arr [i] = 2 ، ما شمارش [arr [i]] + = 1 را انجام خواهیم داد ، به این معنی که شاخص 2 عنصر شمارش 1 افزایش می یابد.

ما آرایه شمارش را به عنوان شمارش داریم [] = {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

تحلیل پیچیدگی

پیچیدگی زمان

O (N) جایی که "n" تعداد عناصر آرایه است. برای دستیابی به عناصر آرایه زمان O (1) لازم است. بنابراین پیچیدگی زمان خطی است.

پیچیدگی فضا

O (حداکثر) ، که در آن Max حداکثر عنصر در بین تمام عناصر موجود در آرایه است.