Пронађите број парова у низу тако да је њихов КСОР 0


Ниво тешкоће Средњи
Често питани у Цаденце Индиа ЦоупонДуниа Хонеивелл Заиста ИнфоЕдге Моонфрог Лабс Пинтерест
Ред Битс Хасх Претраживање сортирање

Проблем „Пронађи број парова у низу тако да је њихов КСОР 0“ стање које претпостављамо, дали смо поредак of интегерс. Изјава о проблему тражи да се сазна број парова присутних у низу који има тај пар Ai КСОР Aj = КСНУМКС.

Напомена: 1 је мање или једнако i, i је мање од j j је мање или једнако н (1 <=i < j<= н).

Пример

Пронађите број парова у низу тако да је њихов КСОР 0

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

Објашњење

Индекс (0,4) и (1,3).

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

Алгоритам

  1. Пронађите максималан елемент присутан у низу.
  2. Направите низ величине (максимални елемент).
  3. Пређите низ, док је и <н (дужина низа).
    1. Броји и чувај фреквенције сваког елемента низа у низу који смо креирали.
  4. Пређите низ бројања, док је и <= максимални елемент.
    1. Да ли излаз = излаз + бројање [и] * (бројање [и] - 1);
  5. Повратни излаз / 2.

Објашњење

Имамо низ целих бројева. Изјава о проблему тражи да се сазна пар присутан у низу тако да Ai КСОР Aj = 0. Користићемо мапирање индекса, што значи да ћемо рачунати учесталост сваког елемента низа тако да их можемо схватити могу ли рачунати [и] * цоунт [и-1] и резултирати у излаз. Да бисте то решили користите поредак и на оном месту елемента низа који делује као индекс низа бројања у коме ћемо похранити фреквенцију наших елемената, па ако се на одређеном месту пронађе број, користићемо га као индекс.

Пронаћи ћемо максимум елемента из низа. А од те максималне величине елемента, направићемо низ, ово је низ пребројавања, који ћемо користити као низ фреквенција. Морамо прећи низ и похранити број сваког елемента низа. Тада ћемо поставити излазну променљиву на 0.

Размотримо пример:

Пример

арр [] = {2, 3, 1, 3, 2} максимална величина низа би била 3.

и = 0, арр [и] = 2, урадићемо цоунт [арр [и]] + = 1, то значи да ће се други индекс бројачког елемента повећати за 2.

и = 1, арр [и] = 3, урадићемо цоунт [арр [и]] + = 1, то значи да ће се други индекс бројачког елемента повећати за 3.

и = 2, арр [и] = 1, урадићемо цоунт [арр [и]] + = 1, то значи да ће се 1. индекс бројачког елемента повећати за 1.

и = 3, арр [и] = 3, урадићемо цоунт [арр [и]] + = 1, то значи да ће се 3. индекс бројачког елемента повећати за 1.

и = 4, арр [и] = 2, урадићемо цоунт [арр [и]] + = 1, то значи да ће се други индекс бројачког елемента повећати за 2.

Имамо матрицу бројања као цоунт [] = {0,1,2,2}

Прећи ћемо овај низ и сваки пут када направимо оутпут = оутпут + цоунт [и] * (цоунт [и] - 1).

И вратиће излаз као оутпут / 2.

Ц ++ код за проналажење броја парова у низу тако да је њихов КСОР 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

Јава код за проналажење броја парова у низу тако да је њихов КСОР 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

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. О (1) време је потребно за приступ елементима у низу. Стога је временска сложеност линеарна.

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

О (макс.), где је Мак максимални елемент међу свим елементима низа.