अ‍ॅरेमध्ये जोड्यांची संख्या शोधा जसे की त्यांचा एक्सओआर 0 आहे


अडचण पातळी मध्यम
वारंवार विचारले कॅडन्स इंडिया कूपनडुनिया हनिवेल खरंच इन्फो एडज मूनफ्रोग लॅब करा
अरे बिट्स हॅश शोधत आहे वर्गीकरण

समजा “अ‍ॅरेमध्ये जोड्यांची संख्या शोधा जसे की त्यांचा एक्सओआर 0 आहे” असे समजू की आम्ही ते दिले अॅरे of पूर्णांक. समस्या विधान अ‍ॅरेमध्ये असलेल्या जोड्यांची संख्या शोधण्यास सांगते, ज्यामध्ये जोड आहे Ai एक्सओआर Aj = 0.

टीपः 1 ही या पेक्षा कमी किंवा त्या समान आहे i, i पेक्षा कमी आहे j आणि j n (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. I <= जास्तीत जास्त घटक असताना गणना अ‍ॅरेचा आढावा घ्या.
    1. आउटपुट = आउटपुट + गणना करा [i] * (गणना [i] - 1);
  5. रिटर्न आउटपुट / २.

स्पष्टीकरण

आपल्याकडे पूर्णांक संख्या आहे. समस्या विधान अशा अ‍ॅरेमध्ये असलेली जोडी शोधण्यासाठी विचारते Ai एक्सओआर Aj = ०. आम्ही अनुक्रमणिका मॅपिंग वापरणार आहोत, म्हणजेच आम्ही प्रत्येक अ‍ॅरे घटकाची वारंवारता मोजणार आहोत जसे की ते मोजू शकले तर आपण त्यांचा आकृती काढू [i] * गणना [i-0] आणि परिणामी आउटपुट हे सोडवण्यासाठी एक अॅरे आणि त्या अ‍ॅरे एलिमेंटच्या त्या जागेवर जी गणना अ‍ॅरेची अनुक्रमणिका म्हणून कार्य करते ज्यामध्ये आपण आपल्या घटकांची वारंवारता संचयित करणार आहोत, म्हणून जर एखाद्या विशिष्ट ठिकाणी एखादी संख्या आढळली तर आम्ही त्यास अनुक्रमणिका म्हणून वापरणार आहोत.

आम्हाला अ‍ॅरेमधून जास्तीत जास्त घटक सापडेल. आणि त्या जास्तीत जास्त घटकाच्या आकारात आपण अ‍ॅरे बनवणार आहोत, ही गणना अ‍ॅरे आहे, याला आपण वारंवारता अ‍ॅरे म्हणून वापरणार आहोत. आपल्याला अ‍ॅरेचा आडवा भाग घेण्याची आणि प्रत्येक अ‍ॅरे घटकांची संख्या संग्रहित करण्याची आवश्यकता आहे. नंतर आउटपुट व्हेरिएबल 0 वर सेट करू.

चला त्याचं उदाहरण घेऊ:

उदाहरण

अरे [] = {2, 3, 1, 3, 2 ray अ‍ॅरेचा जास्तीत जास्त आकार 3 असेल.

i = 0, अरे [i] = 2, आम्ही गणना करू [ar [i]] + = 1, म्हणजे मोजणीच्या घटकाची 2 रा निर्देशांक 1 ने वाढेल.

i = 1, अरे [i] = 3, आम्ही गणना करू [ar [i]] + = 1, म्हणजे मोजणीच्या घटकाची 3 रा निर्देशांक 1 ने वाढेल.

i = 2, अरे [i] = 1, आम्ही गणना करू [ar [i]] + = 1, म्हणजे मोजणीच्या घटकाची पहिली अनुक्रमणिका 1 ने वाढेल.

i = 3, अरे [i] = 3, आम्ही गणना करू [ar [i]] + = 1, म्हणजे मोजणीच्या घटकाची तिसरी अनुक्रमणिका 3 ने वाढेल.

i = 4, अरे [i] = 2, आम्ही गणना करू [ar [i]] + = 1, म्हणजे मोजणीच्या घटकाची 2 रा निर्देशांक 1 ने वाढेल.

आमच्याकडे गणना म्हणून अ‍ॅरे आहेत [] = {0,1,2,2}

आम्ही हा अ‍ॅरे पुढे जाऊ आणि प्रत्येक वेळी आउटपुट = आऊटपुट + गणना [i] * (गणना [i] - 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. अ‍ॅरेमधील घटकांमध्ये प्रवेश करण्यासाठी ओ (1) वेळ आवश्यक आहे. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (कमाल), जेथे अ‍ॅरेमधील सर्व घटकांमधील कमाल हा घटक असतो.