दो सेटों की गैर-अतिव्यापी राशि


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट वीरांगना वृद्धि कुलिजा Pinterest स्नैपडील Synopsys Teradata
ऐरे hashing

समस्या का विवरण

समस्या "दो सेटों की गैर-अतिव्यापी राशि" बताती है कि आपको एक ही आकार के एन [ए] और एआईआरबी [] के रूप में इनपुट मानों के रूप में दो सरणियां दी जाती हैं। इसके अलावा, दोनों सरणियों में अलग-अलग तत्व अलग-अलग हैं और कुछ सामान्य तत्व हैं। आपका कार्य सभी गैर-सामान्य तत्वों के कुल योग का पता लगाना है।

उदाहरण

arrA[] = {1,3,4,5,2}
arrB[] = {2,4,6,7,8}
30

व्याख्या

सरणी के उपरोक्त सेट में विशिष्ट तत्व 1, 3, 5, 6, 7 और 8 हैं।

कुल योग = 1+ 3 + 5 + 6 + 7 +8 = 30 है।

दो सेटों की गैर-अतिव्यापी राशि

 

arrA[]={1,3,4,5,2}
arrB[]={3,4,1,5,7}
9

व्याख्या

सभी तत्व सामान्य हैं इसलिए आउटपुट 0 होगा।

कलन विधि

  1. डिक्लेयर ए नक्शा.
  2. पार कर जाना सरणी जबकि i <n (सरणी की लंबाई)।
    1. सरणी के दोनों तत्वों की आवृत्तियों को मानचित्र में गिनें और संग्रहीत करें।
  3. कुल सेटसम 0 पर।
  4. नक्शे को पार करें।
    1. जाँच करें कि क्या तत्व का मान 1 के बराबर है।
      1. अगर सच है, तो कुल तत्वों में सभी तत्वों को जोड़ते रहें।
  5. कुल वापसी।

 व्याख्या

हमने दो इनपुट एरे दिए हैं जिनमें कुछ तत्व सामान्य हैं। समस्या कथन दोनों एरे के सभी तत्वों के कुल योग का पता लगाने के लिए कहता है जो असामान्य हैं। इसके लिए, हम उपयोग करने जा रहे हैं हैशिंग. हैश मैप कुंजी और मूल्यों के साथ काम करता है, इसमें चाबियाँ होंगी और मूल्य कुंजी के साथ जुड़ा हुआ है। तो यह एक साथ काम करता है। हम एक हैशमैप घोषित करेंगे और एक ही नक्शे में, हम दोनों आवृत्तियों के तत्वों को अपनी आवृत्तियों के साथ मानचित्र में संग्रहीत करने जा रहे हैं।

उदाहरण

आइए एक उदाहरण पर विचार करें: arrA [] = {1,3,4,5,2}, arrB [] = {2,4,6,7,8}

चूँकि दोनों सरणियाँ समान आकार n की हैं। दोनों सरणियों का पता लगाने के दौरान, हमें बस एक समय को पार करने की आवश्यकता है और उस में, हम तत्वों और आवृत्तियों के साथ किया जाएगा। उसके बाद हमारे नक्शे में निम्नलिखित मान होंगे।

नक्शा: {१: १, २: २, ३: १, ४: २, ५: १, ६: १,:: १,:: १}।

वैरिएबल टोटलसम को 0 पर सेट करने के बाद, हमें सभी गैर-सामान्य तत्वों का योग प्राप्त करने के लिए मैप को आगे बढ़ाना होगा। हम स्थिति की जांच करेंगे यदि किसी भी तत्व की आवृत्ति है, वह 1 है, हम केवल उस तत्व को चुनेंगे और उस तत्व और कुल को जोड़ेंगे और कुल योग में संग्रहीत करेंगे।

कुलसुम = 0,

  • मानचित्र के पहले तत्व '1' में 1 आवृत्ति होती है और इसे कुल जोड़ => कुलसम + कुंजी = 0 +1 = 1।
  • मैप के दूसरे तत्व '2' में फ़्रीक्वेंसी 2 है, इसलिए हम उस कुंजी को नहीं लेंगे क्योंकि यह दोनों ऐरे में आम है।
  • मानचित्र के पहले तत्व '3' में 1 आवृत्ति होती है और इसे कुल जोड़ => कुलसम + कुंजी = 1 +3 = 4।
  • मैप के दूसरे तत्व '4' में फ़्रीक्वेंसी 2 है, इसलिए हम उस कुंजी को नहीं लेंगे क्योंकि यह दोनों ऐरे में आम है।
  • मानचित्र के पहले तत्व '5' में 1 आवृत्ति है, हम इसे कुल जोड़ते हैं => कुलसुम + कुंजी = 4 +5 = 9।

इसी तरह हम कुल मिलाकर 6, 7 और 8 को जोड़ेंगे क्योंकि सभी का फ़्रीक्वेंसी के रूप में मूल्य 1 है। तो यह 1+ 3 + 5 + 6 + 7 +8 = 30 हो जाएगा।

आउटपुट: १

कोड

दो सेटों की गैर-अतिव्यापी राशि के लिए C ++ में कार्यान्वयन

#include <unordered_map>
#include<iostream>

using namespace std;

int findSum(int arrA[], int arrB[], int n)
{
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++)
    {
        map[arrA[i]]++;
        map[arrB[i]]++;
    }
    int totalSum = 0;
    for (auto sel: map)
        if (sel.second == 1)
            totalSum += sel.first;

    return totalSum;
}
int main()
{
    int arrA[] = { 5, 1, 10, 4, 7 };
    int arrB[] = { 1, 6, 7, 8, 2 };
    int l = sizeof(arrA) / sizeof(arrA[0]);
    cout << findSum(arrA, arrB, l);
    return 0;
}
35

दो सेटों की गैर-अतिव्यापी राशि के लिए जावा में कार्यान्वयन

import java.util.HashMap;
import java.util.Map;

class nonOverlappingSum
{
    public static int findSum(int[] A, int[] B, int n)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            if (map.containsKey(A[i]))
                map.put(A[i], map.get(A[i]) + 1);
            else
                map.put(A[i], 1);

            if (map.containsKey(B[i]))
                map.put(B[i], map.get(B[i]) + 1);
            else
                map.put(B[i], 1);
        }
        int totalSum = 0;
        for (Map.Entry entry : map.entrySet())
        {
            if (Integer.parseInt((entry.getValue()).toString()) == 1)
                totalSum += Integer.parseInt((entry.getKey()).toString());
        }
        return totalSum;

    }
    public static void main(String args[])
    {
        int arrA[] = { 5, 1, 10, 4, 7 };
        int arrB[] = { 1, 6, 7, 8, 2 };
        int l = arrA.length;
        System.out.println(findSum(arrA, arrB, l));
    }
}
35

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

समय जटिलता

पर) जहां "N" सरणी की लंबाई है। क्योंकि हमने हैशमैप का उपयोग किया है इसलिए ओ (1) समय जटिलता में खोज, विलोपन और अपडेशन के सभी ऑपरेशन किए जा रहे हैं। इस प्रकार हम रैखिक समय जटिलता प्राप्त करने में सक्षम थे।

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

पर) जहां "N" सरणी की लंबाई है। दोनों सरणियों के तत्वों को मानचित्र में संग्रहीत करने के लिए स्थान की आवश्यकता होती है।