দুটি সেটের নন-ওভারল্যাপিং যোগফল


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি মর্দানী স্ত্রীলোক আরোহণ কুলিজা পিন্টারেস্ট Snapdeal সংক্ষেপ তেরদাটা
বিন্যাস হ্যাশ

সমস্যা বিবৃতি

"দুটি সেটগুলির নন-ওভারল্যাপিং সমষ্টি" সমস্যাটিতে বলা হয়েছে যে আপনাকে একই আকারের এনআরএ [] এবং অ্যারেবি [] হিসাবে ইনপুট মান হিসাবে দুটি অ্যারে দেওয়া হবে। এছাড়াও, উভয় অ্যারে পৃথক পৃথক পৃথক উপাদান এবং কিছু সাধারণ উপাদান রয়েছে। আপনার কাজটি সমস্ত অ-সাধারণ উপাদানগুলির মোট যোগফল খুঁজে বের করা।

উদাহরণ

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. অতিক্রম করুন বিন্যাস যখন আমি <এন (অ্যারের দৈর্ঘ্য)।
    1. অ্যারের উভয় উপাদানগুলির ফ্রিকোয়েন্সি মানচিত্রে গণনা করুন এবং সংরক্ষণ করুন।
  3. মোটসুম 0 তে সেট করুন।
  4. মানচিত্রটি অতিক্রম করুন।
    1. মানকের উপাদানটির মান 1 এর সমান কিনা তা পরীক্ষা করুন।
      1. যদি সত্য হয়, তবে মোট উপাদানগুলিতে সমস্ত উপাদান যুক্ত করতে থাকুন।
  5. মোট

 ব্যাখ্যা

আমরা দুটি ইনপুট অ্যারে দিয়েছি যার মধ্যে কিছু উপাদান সাধারণ। সমস্যা বিবৃতিটি উভয় অ্যারেরগুলির সমস্ত উপাদানের সামগ্রীর যোগফল যা অস্বাভাবিক। এই জন্য, আমরা ব্যবহার করতে যাচ্ছি হ্যাশ. হ্যাশ মানচিত্র কী এবং মানগুলির সাথে কাজ করে, এতে কীগুলি থাকবে এবং মানটি কীটির সাথে যুক্ত। সুতরাং এটি একসাথে কাজ করে। আমরা একটি হ্যাশম্যাপ ঘোষণা করব এবং একটি একক মানচিত্রে, আমরা উভয় অ্যারের উপাদানগুলিকে তাদের ফ্রিকোয়েন্সি সহ মানচিত্রে সংরক্ষণ করতে যাচ্ছি।

উদাহরণ

আসুন একটি উদাহরণ বিবেচনা করা যাক: অ্যারে [] = {1,3,4,5,2}, আরআরবি [] = {2,4,6,7,8}

যেহেতু অ্যারে উভয়ই একই আকারের এন। উভয় অ্যারেটি ট্র্যাভার করার সময় আমাদের কেবল একটি সময় অতিক্রম করতে হবে এবং এটিতে, আমরা উপাদান এবং ফ্রিকোয়েন্সিগুলি সম্পন্ন করব। এর পরে আমাদের মানচিত্রে নিম্নলিখিত মান থাকবে।

মানচিত্র: {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1}

ভেরিয়েবল টোটসাম 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 হয়ে যাবে।

আউটপুট: 30

কোড

দুটি সেটের নন-ওভারল্যাপিং যোগফলের জন্য সি ++ এ বাস্তবায়ন

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারের দৈর্ঘ্য। কারণ আমরা অনুসন্ধানের সমস্ত অপারেশন, মুছে ফেলার এবং আপডেট করার জন্য হ্যাশম্যাপ ব্যবহার করেছি ও (1) সময়ের জটিলতায় complex সুতরাং আমরা লিনিয়ার সময় জটিলতা অর্জন করতে সক্ষম হয়েছি।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারের দৈর্ঘ্য। উভয় অ্যারের উপাদানগুলিকে মানচিত্রে সংরক্ষণের জন্য স্থান প্রয়োজন।