Массивтегі жұптардың санын, олардың XOR мәні 0 болатынын табыңыз  


Күрделілік дәрежесі орта
Жиі кіреді Cadence Үндістан КупонDunia Honeywell шынында InfoEdge Moonfrog зертханалары Pinterest
Array Биттер Hash іздеу Сұрыптау

«Массивтегі жұптардың санын табыңыз, егер олардың 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. Do output = output + count [i] * (count [i] - 1);
  5. Шығу нәтижесін қайтару / 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}

Біз бұл массивті айналып өтеміз және әр уақытта шығару = нәтиже + санақ [i] * (санау [и] - 1).

Және бұл нәтижені шығыс ретінде қайтарады / 2.

Массивтегі жұптардың санын, олардың 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 болатындай етіп, Java коды  

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 - массивтің барлық элементтерінің ішіндегі максималды элемент.