രണ്ട് സെറ്റുകളുടെ ഓവർലാപ്പിംഗ് തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ ഉയർത്തൽ കുലിസ പോസ്റ്റ് സ്നാപ്ഡേൽ സമന്വയിപ്പിക്കുക തെരദത
അറേ ഹാഷിംഗ്

പ്രശ്നം പ്രസ്താവന

“രണ്ട് സെറ്റുകളുടെ ഓവർലാപ്പുചെയ്യാത്ത തുക” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് രണ്ട് അറേകൾ ഇൻപുട്ട് മൂല്യങ്ങളായി arrA [], ഒരേ വലുപ്പം n ന്റെ arrB [] എന്നിവ നൽകിയിരിക്കുന്നു. കൂടാതെ, രണ്ട് അറേകൾക്കും വെവ്വേറെ ഘടകങ്ങളും ചില പൊതു ഘടകങ്ങളുമുണ്ട്. സാധാരണമല്ലാത്ത എല്ലാ ഘടകങ്ങളുടെയും ആകെ തുക കണ്ടെത്തുക എന്നതാണ് നിങ്ങളുടെ ചുമതല.

ഉദാഹരണം

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 ട്ട്‌പുട്ട് XNUMX ആയിരിക്കും.

അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  2. സഞ്ചരിക്കുക ശ്രേണി ഞാൻ <n (അറേയുടെ നീളം).
    1. അറേയുടെ രണ്ട് ഘടകങ്ങളുടെയും ആവൃത്തികൾ മാപ്പിലേക്ക് എണ്ണുക, സംഭരിക്കുക.
  3. ടോട്ടൽസം 0 ആയി സജ്ജമാക്കുക.
  4. മാപ്പ് സഞ്ചരിക്കുക.
    1. മൂലകത്തിന്റെ മൂല്യം 1 ന് തുല്യമായ മാപ്പ് ഉണ്ടോയെന്ന് പരിശോധിക്കുക.
      1. ശരിയാണെങ്കിൽ, എല്ലാ ഘടകങ്ങളും ടോട്ടൽ‌സുമിലേക്ക് ചേർക്കുന്നത് തുടരുക.
  5. ടോട്ടൽസം മടങ്ങുക.

 വിശദീകരണം

ചില ഘടകങ്ങൾ‌ പൊതുവായുള്ള രണ്ട് ഇൻ‌പുട്ട് അറേകൾ‌ ഞങ്ങൾ‌ നൽ‌കി. അസാധാരണമായ രണ്ട് അറേകളുടെയും എല്ലാ ഘടകങ്ങളുടെയും ആകെത്തുക കണ്ടെത്താൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു. ഇതിനായി, ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ്. ഹാഷ്‌മാപ്പ് കീയും മൂല്യങ്ങളും ഉപയോഗിച്ച് പ്രവർത്തിക്കുന്നു, അതിന് കീകൾ ഉണ്ടാകും, ഒപ്പം മൂല്യം കീയുമായി ബന്ധപ്പെട്ടിരിക്കുന്നു. അതിനാൽ ഇത് ഒരുമിച്ച് പ്രവർത്തിക്കുന്നു. ഞങ്ങൾ ഒരു ഹാഷ്‌മാപ്പ് പ്രഖ്യാപിക്കും, ഒരൊറ്റ മാപ്പിൽ, രണ്ട് അറേകളുടെയും ഘടകങ്ങൾ അവയുടെ ആവൃത്തി ഉപയോഗിച്ച് മാപ്പിൽ സംഭരിക്കാൻ പോകുന്നു.

ഉദാഹരണം

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം: arrA [] = {1,3,4,5,2}, arrB [] = {2,4,6,7,8}

രണ്ട് അറേകളും ഒരേ വലുപ്പമുള്ളതിനാൽ n. രണ്ട് അറേകളിലൂടെയും സഞ്ചരിക്കുമ്പോൾ നമുക്ക് ഒരു തവണ സഞ്ചരിക്കേണ്ടതുണ്ട്, അതിൽ, ഘടകങ്ങളും ആവൃത്തികളും ഉപയോഗിച്ച് ഞങ്ങൾ ചെയ്യപ്പെടും. അതിനുശേഷം ഞങ്ങളുടെ മാപ്പിന് ഇനിപ്പറയുന്ന മൂല്യങ്ങൾ ഉണ്ടാകും.

മാപ്പ്: {1: 1, 2: 2, 3: 1, 4: 2, 5: 1, 6: 1, 7: 1, 8: 1}.

ടോട്ടൽ‌സം എന്ന വേരിയബിൾ‌ 0 ആയി സജ്ജമാക്കിയതിനുശേഷം, പൊതുവായ ഇതര ഘടകങ്ങളുടെ ആകെത്തുക ലഭിക്കുന്നതിന് ഞങ്ങൾ‌ മാപ്പിലൂടെ സഞ്ചരിക്കേണ്ടതുണ്ട്. ഏതെങ്കിലും മൂലകത്തിന് ആവൃത്തി ഉണ്ടോയെന്ന് ഞങ്ങൾ പരിശോധിക്കും, അതായത് 1, ഞങ്ങൾ ആ ഘടകം തിരഞ്ഞെടുത്ത് ആ ഘടകവും ടോട്ടൽസും ചേർത്ത് ടോട്ടൽസാമിലേക്ക് സംഭരിക്കും.

totalSum = 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 ആയി മാറും.

Put ട്ട്‌പുട്ട്: 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയുടെ നീളം. ഞങ്ങൾ ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ തിരയൽ, ഇല്ലാതാക്കൽ, അപ്‌ഡേറ്റ് എന്നിവയുടെ എല്ലാ പ്രവർത്തനങ്ങളും O (1) സമയ സങ്കീർണ്ണതയിലാണ് ചെയ്യുന്നത്. അങ്ങനെ ലീനിയർ സമയ സങ്കീർണ്ണത കൈവരിക്കാൻ ഞങ്ങൾക്ക് കഴിഞ്ഞു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയുടെ നീളം. രണ്ട് അറേകളുടെയും ഘടകങ്ങൾ മാപ്പിൽ സംഭരിക്കുന്നതിന് ഇടം ആവശ്യമാണ്.