XOR이 0이되도록 배열에서 쌍 수 찾기


난이도 중급
자주 묻는 질문 케이던스 인도 쿠폰 Dunia 하니웰 과연 InfoEdge 문 프로그 연구소 클립
배열 비트 해시 수색 정렬

"XOR이 0이되도록 배열에서 쌍의 수를 찾으십시오"라는 문제는 다음과 같이 가정합니다. 정렬 of 정수. 문제 설명은 한 쌍이있는 배열에있는 쌍의 수를 알아 내도록 요청합니다. Ai 무료 Aj = 0.

참고 : 1은 다음보다 작거나 같습니다. i, i ~보다 작다. jj 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 무료 Aj = 0. 인덱스 매핑을 사용할 것입니다. 즉, 각 배열 요소의 빈도를 계산하여 count [i] * count [i-1]을 수행 할 수 있고 그 결과 산출. 이 문제를 해결하려면 정렬 그리고 계수 배열의 인덱스 역할을하는 배열 요소의 위치에서 요소 빈도를 저장할 것이므로 특정 위치에서 숫자가 발견되면이를 인덱스로 사용할 것입니다.

배열에서 최대 요소를 찾습니다. 그리고 그 최대 요소 크기 중에서 배열을 만들 것입니다. 이것은 카운트 배열입니다. 이것은 주파수 배열로 사용할 것입니다. 배열을 순회하고 각 배열 요소의 개수를 저장해야합니다. 그런 다음 출력 변수를 0으로 설정합니다.

예를 들어 보겠습니다.

arr [] = {2, 3, 1, 3, 2} 배열의 최대 크기는 3입니다.

i = 0, arr [i] = 2, count [arr [i]] + = 1, 즉 count 요소의 두 번째 인덱스가 2 씩 증가 함을 의미합니다.

i = 1, arr [i] = 3, count [arr [i]] + = 1, 즉 count 요소의 두 번째 인덱스가 3 씩 증가 함을 의미합니다.

i = 2, arr [i] = 1, count [arr [i]] + = 1, count 요소의 첫 번째 인덱스가 1 씩 증가 함을 의미합니다.

i = 3, arr [i] = 3, count [arr [i]] + = 1, 즉 count 요소의 세 번째 인덱스가 3 씩 증가 함을 의미합니다.

i = 4, arr [i] = 2, count [arr [i]] + = 1, 즉 count 요소의 두 번째 인덱스가 2 씩 증가 함을 의미합니다.

count의 배열은 count [] = {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

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) 어디에 "엔" 배열의 요소 수입니다. 배열의 요소에 액세스하려면 O (1) 시간이 필요합니다. 따라서 시간 복잡도는 선형입니다.

공간 복잡성

O (최대), 여기서 Max는 배열의 모든 요소 중 최대 요소입니다.