Массивдеги XOR саны 0 болгон жуптардын санын табыңыз


Кыйынчылык деңгээли орто
Көп суралган Каденс Индия CouponDunia ЭлЭлПи Чындыгында InfoEdge Moonfrog Labs Pinterest
согуштук тизме 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

Algorithm

  1. Массивдеги эң жогорку элементти билип алыңыз.
  2. Көлөм массивин түзүңүз (максималдуу элемент).
  3. Массивди айланып өтүңүз, ал эми i <n (массивдин узундугу).
    1. Ар бир массив элементинин жыштыгын санап, биз түзгөн массивде сактаңыз.
  4. Санак массивин айланып өтүңүз, i <= максималдуу элемент.
    1. Do output = output + count [i] * (count [i] - 1);
  5. Return output / 2.

түшүндүрүү

Бизде бир катар сандар бар. Маселе билдирүүсү массивдеги жупту табууну суранат Ai XOR Aj = 0. Индекс картасын колдонобуз, демек, массивдин ар бир элементинин жыштыгын эсептейбиз, эгерде аларды [i] * count [i-1] кылып, натыйжасында чыгаруу. Муну чечүү үчүн согуштук тизме ал эми массив элементинин ошол жеринде, биз элементтердин жыштыгын сактай турган эсептөө массивинин индекси катары иштейбиз, андыктан белгилүү бир жерде сан табылса, биз аны индекс катары колдонобуз.

Массивден максималдуу элементти табабыз. Жана ушул элементтин максималдуу өлчөмүнөн биз массив жасайбыз, бул сан массив, биз аны жыштык массиви катары колдонобуз. Биз массивден өтүшүбүз керек жана ар бир массив элементтеринин эсептөөсүн сакташыбыз керек. Андан кийин чыгуучу өзгөрмөнү 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-индекси 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}

Биз бул массивден өтөбүз жана чыгарган сайын output = output + count [i] * (count [i] - 1).

Жана ал чыгарууну output / 2 деп кайтарып берет.

Массивдеги жуптардын санын, алардын XOR саны 0 болгон кодду табуу үчүн C ++ коду

#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 (Max), бул жерде Max - массивдеги бардык элементтердин арасынан эң чоң элемент.