Rayանգվածում գտեք զույգերի քանակ, այնպես, որ դրանց XOR- ը 0 լինի


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Կադենս Հնդկաստան CouponDunia HONEYWELL Իսկապես InfoEdge Moonfrog լաբորատորիաներ Pinterest
Դասավորություն Բիթեր Խանգարել Որոնում դասավորում

«Anանգվածի մեջ գտեք զույգերի քանակը այնպես, որ դրանց XOR- ը 0 լինի» խնդիրը, որը ենթադրում է, որ մենք տվել ենք դասավորություն of ամբողջական թվերը, Խնդրի հայտարարությունը խնդրում է պարզել զանգվածում առկա զույգերի քանակը, որն ունի զույգը Ai XOR- ը Aj = 0.

Նշում. 1-ը պակաս է կամ հավասար է դրան i, i պակաս է j և j պակաս է կամ հավասար է n (1 <=i < j<= n)

Օրինակ

Rayանգվածում գտեք զույգերի քանակ, այնպես, որ դրանց 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. Մենք պատրաստվում ենք օգտագործել ինդեքսի քարտեզագրում, ինչը նշանակում է, որ մենք հաշվելու ենք յուրաքանչյուր զանգվածի տարրերի հաճախականությունը այնպես, որ կարողանանք պարզել, եթե նրանք կարող են հաշվել [i] * հաշվել [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] * (հաշվել [i] - 1):

Եվ դա արդյունքը կվերադարձնի որպես ելք / 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: (Անգվածի տարրերը մուտք գործելու համար պահանջվում է O (1) ժամանակ: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

Ո (առավելագույն), որտեղ Max- ը զանգվածի բոլոր տարրերի մեջ առավելագույն տարրն է: