Намерете брой двойки в масив, така че техният XOR да е 0


Ниво на трудност M
Често задавани в Каденс Индия CouponDunia Honeywell Наистина InfoEdge Moonfrog Labs Pinterest
Array 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. Ще използваме картографиране на индекса, което означава, че ще преброим честотата на всеки елемент на масив, така че да можем да ги разберем дали могат да направят count [i] * count [i-1] и резултатът в изход. За да разрешите това, използвайте масив и в това място на елемент на масив, който действа като индекс на масив от броене, в който ще съхраняваме честотата на нашите елементи, така че ако дадено число бъде намерено на определено място, ще го използваме като индекс.

Ще намерим максималния елемент от масива. И от този максимален размер на елемента ще направим масив, това е брой масив, това ще използваме като честотен масив. Трябва да прекосим масива и да съхраним броя на всеки елемент от масива. След това ще зададем изходната променлива на 0.

Нека разгледаме един пример:

Пример

arr [] = {2, 3, 1, 3, 2} максималният размер на масива ще бъде 3.

i = 0, arr [i] = 2, ще направим count [arr [i]] + = 1, това означава, че 2-ри индекс на елемента на count ще бъде увеличен с 1.

i = 1, arr [i] = 3, ще направим count [arr [i]] + = 1, това означава, че 3-ри индекс на елемента на count ще бъде увеличен с 1.

i = 2, arr [i] = 1, ще направим count [arr [i]] + = 1, това означава, че 1-вият индекс на елемента на count ще бъде увеличен с 1.

i = 3, arr [i] = 3, ще направим count [arr [i]] + = 1, това означава, че 3-тият индекс на елемента на count ще бъде увеличен с 1.

i = 4, arr [i] = 2, ще направим count [arr [i]] + = 1, това означава, че 2-ри индекс на елемента на count ще бъде увеличен с 1.

Имаме масива на count като count [] = {0,1,2,2}

Ще прекосим този масив и всеки път, когато направим изход = изход + брой [i] * (count [i] - 1).

И ще върне изхода като output / 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 (1) време е необходимо за достъп до елементите в масива. По този начин сложността на времето е линейна.

Сложност на пространството

O (макс.), където Max е максималният елемент сред всички елементи в масива.