מצא את מספר הזוגות במערך כך שה- XOR שלהם הוא 0


רמת קושי בינוני
נשאל לעתים קרובות קדנס הודו קופון דוניה Honeywell אכן InfoEdge מעבדות מונפרוג פינטרסט
מערך Bits בליל חיפוש מִיוּן

הבעיה "מצא מספר זוגות במערך כך ש- 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).

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

אַלגוֹרִיתְם

  1. גלה את האלמנט המרבי הקיים במערך.
  2. צור מערך בגודל (אלמנט מקסימאלי).
  3. חצו את המערך, בעוד i <n (אורך המערך).
    1. ספרו ואחסנו את התדרים של כל אלמנט מערך במערך שיצרנו.
  4. חצו את מערך הספירה, בעוד i <= אלמנט מקסימאלי.
    1. האם פלט = פלט + ספירה [i] * (ספירה [i] - 1);
  5. תפוקת החזר / 2.

הסבר

יש לנו מערך של מספרים שלמים. הצהרת הבעיה מבקשת לגלות את הצמד שנמצא במערך כזה Ai XOR Aj = 0. אנו משתמשים במיפוי אינדקסים, כלומר אנו נספור את התדירות של כל אלמנט מערך כך שנוכל להבין אם הם יכולים לספור [i] * לספור [i-1] וכתוצאה מכך תְפוּקָה. כדי לפתור שימוש זה מערך ובאותו מקום של אלמנט מערך המשמש אינדקס של מערך ספירה בו אנו הולכים לאחסן את תדר האלמנטים שלנו, כך שאם נמצא מספר במקום מסוים, אנו נשתמש בו כאינדקס.

מצאנו את האלמנט המרבי מהמערך. ומגודל האלמנט המרבי הזה, אנחנו הולכים ליצור מערך, זה מערך ספירה, זה אנחנו נשתמש כמערך תדרים. עלינו לחצות את המערך ולאחסן את ספירת כל אלמנט המערך. לאחר מכן נגדיר את משתנה הפלט ל- 0.

הבה נבחן דוגמה:

דוגמה

arr [] = {2, 3, 1, 3, 2} הגודל המרבי של המערך יהיה 3.

i = 0, arr [i] = 2, אנו נספור [arr [i]] + = 1, זה אומר שהמדד השני של אלמנט הספירה יגדל ב -2.

i = 1, arr [i] = 3, אנו נספור [arr [i]] + = 1, זה אומר שהמדד השני של אלמנט הספירה יגדל ב -3.

i = 2, arr [i] = 1, אנחנו נספור [arr [i]] + = 1, זה אומר שהאינדקס הראשון של אלמנט הספירה יגדל ב -1.

i = 3, arr [i] = 3, אנו נספור [arr [i]] + = 1, זה אומר שהמדד השלישי של אלמנט הספירה יגדל ב -3.

i = 4, arr [i] = 2, אנו נספור [arr [i]] + = 1, זה אומר שהמדד השני של אלמנט הספירה יגדל ב -2.

יש לנו את מערך הספירה כספירה [] = {0,1,2,2}

נחצה את המערך הזה, ובכל פעם שנבצע פלט = פלט + ספירה [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

קוד 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

ניתוח מורכבות

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך. זמן O (1) נדרש לגישה לאלמנטים במערך. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (מקסימום), כאשר מקס הוא האלמנט המרבי בין כל האלמנטים במערך.