એરેના બે સબસેટ્સનો મહત્તમ શક્ય તફાવત


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે Atlassian કેડન્સ ભારત ડાયરેક્ટિ ફ્રીચાર્જ ઓપેરા પે Snapchat ટાઇમ્સ ઇન્ટરનેટ Xome
અરે હેશ સોર્ટિંગ

માની લો, અમારી પાસે એક છે પૂર્ણાંક એરે. સમસ્યા નિવેદન “એરેના બે પેટા સબમિટનો મહત્તમ શક્ય તફાવત” એરેના બે સબસિટો વચ્ચે મહત્તમ શક્ય તફાવત શોધવા માટે પૂછે છે.

શરતોનું પાલન કરવું:

  • એરેમાં પુનરાવર્તન તત્વો શામેલ હોઈ શકે છે, પરંતુ તત્વની સૌથી વધુ આવર્તન 2 કરતા વધારે ન હોવી જોઈએ.
  • તમારે બે સબસેટ્સ બનાવવું જોઈએ જેથી તેમના સંબંધિત તત્વોના સરવાળો વચ્ચેનો તફાવત મહત્તમ હોય.
  • એરેના બધા તત્વોને કોઈપણ ઘટકને પાછળ રાખ્યા વિના બે પેટાની વચ્ચે વહેંચવામાં આવવી જોઈએ.
  • સબસેટમાં બે તત્વો સમાન ન હોવા જોઈએ.

ઉદાહરણ

એરેના બે સબસેટ્સનો મહત્તમ શક્ય તફાવત

arr[] = {2, 5, -3, -1, 5, 7}
13

સમજૂતી

સબસેટ → (2, 7, 5) - (-3, -1, 5) = 13

{1, 5, 3, -1, -5, 6}
21

સમજૂતી

સબસેટ → (1, 3, 5, 6) - (-5, -1) = 21

અલ્ગોરિધમ

  1. બે જાહેર કરો નકશા, એક સકારાત્મક માટે અને એક નકારાત્મક તત્વ માટે.
  2. સકારાત્મક તત્વો અને તેમની ગણતરી એક નકશામાં કરો.
  3. આવર્તન 1 ધરાવતા બધા સકારાત્મક તત્વો ઉમેરવાનું ચાલુ રાખો અને તેને સ્ટોર કરો સબસેટ 1.
  4. નકારાત્મક તત્વ અને તેની ગણતરી બીજા નકશામાં સ્ટોર કરો.
  5. આવર્તન 1 ધરાવતા બધા નકારાત્મક તત્વો ઉમેરવાનું ચાલુ રાખો અને તેને સ્ટોર કરો સબસેટ 2.
  6. સબસેટ 1-સબસેટ 2 પરત કરો.

સમજૂતી

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

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

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

બધી હકારાત્મક અને નકારાત્મક તત્વોની સ્થિતિ પછી, ફક્ત આવર્તન 1 ધરાવતા તત્વોનો સમાવેશ થતાં, આપણે બંને રકમનો તફાવત પાછો આપવો જરૂરી છે અને તે આપણો જવાબ હશે.

કોડ

એરેના બે ઉપગણોનો મહત્તમ શક્ય તફાવત શોધવા માટે સી ++ કોડ

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

એરેના બે ઉપગણોનો મહત્તમ શક્ય તફાવત શોધવા માટે જાવા કોડ

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

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

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે અમે હેશમેપનો ઉપયોગ કર્યો છે અમે ઓ (1) માં નિવેશ / કાtionી નાખવા / શોધવામાં સક્ષમ છીએ.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.