מאַקסימום מעגלעך חילוק פון צוויי סובסעץ פון אַ מענגע  


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַטלאַססיאַן קאַדענס ינדיאַ דירעקטי פרעעטשאַרגע אָפּערע PayU Snapchat Times אינטערנעט 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. דערקלערן צוויי מאַפּס, איינער פֿאַר positive און איינער פֿאַר די נעגאַטיוו עלעמענט.
  2. סטאָר די positive עלעמענטן און זייער ציילן אין איין מאַפּע.
  3. פאָרזעצן צו לייגן אַלע positive עלעמענטן מיט אָפטקייַט 1 און סטאָרד עס סובסעט 1.
  4. קראָם דעם נעגאַטיוו עלעמענט און זיין ציילן אין אן אנדער מאַפּע.
  5. האַלטן אַלע די נעגאַטיוו עלעמענטן וואָס האָבן אָפטקייַט 1 און סטאָרד עס סובסעט 2.
  6. ווייַזן סובסעט 1-סובסעט 2.
זע אויך
גרופּע ווערטער מיט דער זעלביקער סכום פון אותיות

דערקלערונג

מיר האָבן געגעבן אַן מענגע, מיר דאַרפֿן צו געפֿינען די חילוק צווישן די סומע פון ​​עלעמענטן פון צוויי סובסעץ און וואָס זאָל זיין מאַקסימום. מיר וועלן נוצן אַ מאַפּע. האַשינג גיט אַן עפעקטיוו וועג צו סאָלווע דעם קשיא. מיר וועלן נוצן צוויי מאַפּס. איינער איז פֿאַר דורכגעקאָכט אַפּעריישאַנז אויף positive עלעמענטן און אן אנדער פֿאַר די נעגאַטיוו עלעמענטן. אַ מענגע קענען אַנטהאַלטן positive און נעגאַטיוו עלעמענטן ביידע, אַזוי מיר מוזן אויך האַנדלען מיט די זאַך.

מיר וועלן נעמען אַ מענגע און מאַפּע. מיר וועלן קלייַבן יעדער עלעמענט פון דער מענגע און קאָנטראָלירן אויב עס איז גרעסער ווי 0. דערנאָך מיר וועלן צו קראָם עס אין די מאַפּע מיט די נומער פון פֿאַלן. נאָך סטאָרד די פריקוואַנסיז פון די positive עלעמענטן, מיר וועלן צונויפנעמען אַלע די וואַלועס פון אַ מענגע וואָס זענען גרעסער ווי 0 און אויך האָבן אַ אָפטקייַט פון בלויז 1, אַזוי מיר דאַרפֿן צו איגנאָרירן די עלעמענטן וואָס קומען עטלעכע מאָל אָדער מער ווי אַמאָל.

די זעלבע זאַך וועט זיין געטאן מיט נעגאַטיוו עלעמענטן, מיר קלייַבן יעדער עלעמענט פון אַ מענגע און דאָס מאָל מיר וועלן קאָנטראָלירן אויב עס איז ווייניקער ווי 0. מיר וועלן צו קראָם עס אין די מאַפּע (מאכן עס אַ positive נומער) מיט זיין נומער פון פֿאַלן. נאָך סטאָרידזש פרעקווענסיעס פון נעגאַטיוו עלעמענטן, מיר וועלן צוגעלייגט אַלע די וואַלועס פון אַ מענגע וואָס זענען ווייניקער ווי 0 און די אָפטקייַט איז בלויז 1. דאָ מיר אויך דאַרפֿן צו איגנאָרירן די עלעמענטן וואָס קומען עטלעכע מאָל אָדער מער ווי אַמאָל.

זע אויך
קוק פֿאַר פּאַלינדראָמע נאָך יעדער אָנפֿרעג פון כאַראַקטער

נאָך די סאַכאַקל פון אַלע די positive און נעגאַטיוו עלעמענטן צושטאַנד אַז די עלעמענטן האָבן בלויז אָפטקייַט 1, מיר דאַרפֿן צו ווייַזן די דיפעראַנסיז פון ביידע סאַמז און דאָס וואָלט זיין אונדזער ענטפער.

קאָדעקס  

C ++ קאָד צו געפֿינען די מאַקסימום מעגלעך חילוק פון צוויי סובסעץ פון אַ מענגע

#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

Java קאָד צו געפֿינען מאַקסימום מעגלעך דיפעראַנסיז פון צוויי סובסעץ פון אַ מענגע

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

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע. ווייַל מיר האָבן געוויינט האַשמאַפּ, מיר קענען דורכפירן ינסערשאַן / דילישאַן / זוכן אין אָ (1).

זע אויך
געפֿינען נומערן מיט אפילו נומער פון דידזשאַץ לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע.