अ‍ॅरेच्या दोन उपसमूहांमध्ये जास्तीत जास्त शक्य फरक


अडचण पातळी हार्ड
वारंवार विचारले Atlassian कॅडन्स इंडिया डायरेक्टि फ्रीचार्ज ऑपेरा पीएयू Snapchat टाइम्स इंटरनेट झोम
अरे हॅश वर्गीकरण

समजा, आपल्याकडे एक आहे पूर्णांक अॅरे. अ‍ॅरेच्या दोन उपसमूहांमधील जास्तीत जास्त संभाव्य फरक शोधण्यासाठी "स्टेटमेंट ऑफ अ‍ॅरेच्या दोन सबसटट्सचा जास्तीत जास्त संभाव्य फरक" समजू शकते.

पालन ​​करण्याच्या अटीः

  • अ‍ॅरेमध्ये पुनरावृत्ती करणारे घटक असू शकतात परंतु घटकांची सर्वाधिक वारंवारता 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 असणार्‍या घटकांनी, आम्हाला दोन्ही बेरीजचा फरक परत करणे आवश्यक आहे आणि तेच आपले उत्तर असेल.

कोड

अ‍ॅरेच्या दोन उपसमूहांमधील जास्तीत जास्त शक्य फरक शोधण्यासाठी सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही हॅशमॅप वापरल्यामुळे आम्ही ओ (1) मध्ये अंतर्भूत करणे / हटविणे / शोधणे सक्षम आहोत.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.