બે સેટનો ન Nonન-ઓવરલેપિંગ સરવાળો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન પર્યટન કુલીઝા Pinterest સ્નેપડીલ સારાંશ તેરાદાતા
અરે હેશિંગ

સમસ્યા નિવેદન

સમસ્યા "બે સેટનો ન Nonન-ઓવરલેપિંગ સરવાળો" જણાવે છે કે તમને એઆરએ [] અને ઇનરબી [] સમાન કદ એન તરીકે ઇનપુટ મૂલ્યો તરીકે બે એરે આપવામાં આવે છે. ઉપરાંત, બંને એરેમાં વ્યક્તિગત રીતે વિશિષ્ટ તત્વો અને કેટલાક સામાન્ય ઘટકો હોય છે. તમારું કાર્ય એ બધા બિન-સામાન્ય તત્વોની કુલ રકમ શોધવા માટે છે.

ઉદાહરણ

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 છે.

બે સેટનો ન Nonન-ઓવરલેપિંગ સરવાળો

 

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

સમજૂતી

બધા તત્વો સામાન્ય છે તેથી આઉટપુટ 0 હશે.

અલ્ગોરિધમ

  1. ઘોષણા કરો એ નકશો.
  2. આ પસાર એરે જ્યારે હું <એન (એરેની લંબાઈ).
    1. નકશામાં એરેના બંને તત્વોની આવર્તન ગણતરી અને સંગ્રહિત કરો.
  3. કુલસમ 0 પર સેટ કરો.
  4. નકશો પસાર કરો.
    1. તપાસો કે નકશામાં તત્વનું મૂલ્ય 1 હશે.
      1. જો સાચું હોય, તો પછી કુલ તત્વોમાં તત્વો ઉમેરવાનું ચાલુ રાખો.
  5. પરત કુલ

 સમજૂતી

અમે બે ઇનપુટ એરે આપી છે જેમાં કેટલાક તત્વો સામાન્ય છે. સમસ્યા નિવેદનમાં એરે બંનેના તત્વોના કુલ સરવાળા શોધવા માટે પૂછવામાં આવે છે જે અસામાન્ય છે. આ માટે, આપણે ઉપયોગમાં લઈશું હેશીંગ. હાશમpપ કી અને મૂલ્યો સાથે કાર્ય કરે છે, તેમાં કી હશે અને મૂલ્ય કી સાથે સંકળાયેલ છે. તેથી તે સાથે કામ કરે છે. અમે હેશમેપ જાહેર કરીશું અને એક જ નકશામાં, અમે બંને એરેના ઘટકો તેમની ફ્રીક્વન્સીઝ સાથે નકશામાં સંગ્રહિત કરીશું.

ઉદાહરણ

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ: એઆરએ [] = 1,3,4,5,2 2,4,6,7,8}, એઆરબી [] = {XNUMX}

બંને એરે સમાન કદના છે. બંને એરેને ટ્રversવર્સ કરતી વખતે આપણે ફક્ત એક જ સમય પસાર કરવાની જરૂર છે અને તેમાં, અમે તત્વો અને આવર્તન સાથે કરવામાં આવશે. તે પછી અમારા નકશામાં નીચેના મૂલ્યો હશે.

નકશો: {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 અને adding ઉમેરીશું કારણ કે બધાંનાં ફ્રીક્વન્સી તરીકે મૂલ્ય ૧ હોય છે. તેથી તે 7+ 8 + 1 + 1 + 3 +5 = 6 બનશે.

આઉટપુટ: 30

કોડ

બે સેટના ન Nonન-ઓવરલેપિંગ સરવાળો માટે સી ++ માં અમલીકરણ

#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

બે સેટના ન Nonન-ઓવરલેપિંગ સરવાળો માટે જાવામાં અમલીકરણ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેની લંબાઈ છે. કારણ કે અમે હેશમેપનો ઉપયોગ શોધના તમામ કાર્યો, કાtionી નાખવા અને અપડેટ કરવા માટે ઓ (1) સમયની જટિલતામાં કરી રહ્યા છે. આમ અમે રેખીય સમયની જટિલતા પ્રાપ્ત કરવામાં સમર્થ હતા.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેની લંબાઈ છે. નકશામાં બંને એરેના તત્વોને સંગ્રહિત કરવા માટે જગ્યા આવશ્યક છે.