किसी सरणी में जोड़े की संख्या ज्ञात करें जैसे कि उनका XOR 0 है  


कठिनाई स्तर मध्यम
में अक्सर पूछा ताल भारत कूपनदुनिया हनीवेल वास्तव में जानकारी मूनफ्रॉग लैब्स Pinterest
ऐरे बिट्स हैश खोजना छंटाई

समस्या "एक XOR में जोड़े की संख्या ज्ञात करें जैसे कि उनका XOR 0 है" स्थिति जो मानती है, हमने ए दी है सरणी of पूर्णांकों। समस्या कथन एक सरणी में मौजूद जोड़े की संख्या का पता लगाने के लिए कहता है, जिसमें जोड़ी है Ai XOR Aj = 0.

नोट: 1 से कम या इसके बराबर है i, i से कम है j और j n (1 <= से कम या बराबर हैi < j<= एन)।

उदाहरण  

किसी सरणी में जोड़े की संख्या ज्ञात करें जैसे कि उनका XOR 0 हैपिन

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

व्याख्या

सूचकांक (0,4) और (1,3)।

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

कलन विधि  

  1. किसी सरणी में मौजूद अधिकतम तत्व का पता लगाएं।
  2. आकार की एक सरणी (अधिकतम तत्व) बनाएँ।
  3. सरणी को पीछे ले जाएं, जबकि मैं <n (सरणी की लंबाई)।
    1. हमारे द्वारा बनाए गए सरणी में प्रत्येक सरणी तत्व की आवृत्तियों को गिनें और संग्रहीत करें।
  4. गिनती सरणी को पार करें, जबकि मैं <= अधिकतम तत्व।
    1. आउटपुट करना = आउटपुट + गणना [i] * (गिनती [i] - १);
  5. वापसी आउटपुट / 2।

व्याख्या

हमारे पास पूर्णांक की एक सरणी है। समस्या कथन किसी सरणी में मौजूद युग्म का पता लगाने के लिए कहता है जैसे Ai XOR Aj = 0. हम इंडेक्स मैपिंग का उपयोग करने जा रहे हैं, जिसका अर्थ है कि हम प्रत्येक एरे तत्व की आवृत्ति को गिनने जा रहे हैं, ताकि हम यह पता लगा सकें कि क्या वे गणना कर सकते हैं [i] * गिनती [i-1] और परिणामी। आउटपुट। इस उपयोग को हल करने के लिए a सरणी और सरणी तत्व के उस स्थान पर, जो गिनती सरणी के सूचकांक के रूप में कार्य करता है जिसमें हम अपने तत्वों की आवृत्ति को संग्रहीत करने जा रहे हैं, इसलिए यदि कोई स्थान किसी विशेष स्थान पर पाया जाता है, तो हम इसे एक सूचकांक के रूप में उपयोग करने जा रहे हैं।

यह भी देखें
बाइनरी एरे पर गणना और टॉगल क्वेरी करें

हमें सरणी से अधिकतम तत्व मिलेगा। और उस अधिकतम तत्व आकार में, हम एक सरणी बनाने जा रहे हैं, यह गिनती सरणी है, यह हम एक आवृत्ति सरणी के रूप में उपयोग करने जा रहे हैं। हमें ऐरे को पार करना होगा और प्रत्येक ऐरे एलिमेंट की गिनती को स्टोर करना होगा। फिर हम आउटपुट वेरिएबल को 0 पर सेट करेंगे।

चलिए, हम एक उदाहरण पर विचार करते हैं:

उदाहरण

arr [] = {2, 3, 1, 3, 2} सरणी का अधिकतम आकार 3 होगा।

i = 0, arr [i] = 2, हम काउंट करेंगे [arr [i]] + = 1, इसका मतलब है कि count के एलिमेंट का 2nd इंडेक्स 1 से बढ़ जाएगा।

i = 1, arr [i] = 3, हम काउंट करेंगे [arr [i]] + = 1, इसका मतलब है कि count के एलिमेंट का 3nd इंडेक्स 1 से बढ़ जाएगा।

i = 2, arr [i] = 1, हम काउंट करेंगे [arrest [i]] + = 1, इसका मतलब है कि काउंट एलिमेंट के 1st इंडेक्स में 1 की बढ़ोतरी होगी।

i = 3, arr [i] = 3, हम काउंट करेंगे [arrest [i]] + = 1, इसका मतलब है कि count के एलीमेंट का 3rd इंडेक्स 1 से बढ़ जाएगा।

i = 4, arr [i] = 2, हम काउंट करेंगे [arr [i]] + = 1, इसका मतलब है कि count के एलिमेंट का 2nd इंडेक्स 1 से बढ़ जाएगा।

हमारे पास गिनती के रूप में गिनती है [] = {0,1,2,2}

हम इस सरणी को पार करेंगे, और हर बार हम आउटपुट = आउटपुट + काउंट [i] * (काउंट [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 है  

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

जटिलता विश्लेषण  

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। सरणी में तत्वों तक पहुंचने के लिए ओ (1) समय की आवश्यकता होती है। इस प्रकार समय जटिलता रैखिक है।

यह भी देखें
सॉर्ट किए गए घुमाए गए सरणी में एक तत्व खोजें

अंतरिक्ष जटिलता

ओ (अधिकतम), जहाँ सरणी में सभी तत्वों के बीच अधिकतम तत्व है।