శ్రేణి యొక్క రెండు ఉపసమితుల గరిష్ట వ్యత్యాసం


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది Atlassian కాడెన్స్ ఇండియా డైరెక్టి ఫ్రీచార్జ్ ఒపేరా PayU Snapchat టైమ్స్ ఇంటర్నెట్ Xome
అర్రే హాష్ సార్టింగ్

మనకు ఒక ఉంది అనుకుందాం పూర్ణ సంఖ్య అమరిక. సమస్య ప్రకటన “శ్రేణి యొక్క రెండు ఉపసమితుల గరిష్ట వ్యత్యాసం” శ్రేణి యొక్క రెండు ఉపసమితుల మధ్య గరిష్ట వ్యత్యాసాన్ని తెలుసుకోవడానికి అడుగుతుంది.

అనుసరించాల్సిన షరతులు:

  • శ్రేణి పునరావృత మూలకాలను కలిగి ఉంటుంది, కానీ ఒక మూలకం యొక్క అత్యధిక పౌన frequency పున్యం 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 తిరిగి.

వివరణ

మేము ఒక ఇచ్చాము అమరిక, మేము రెండు ఉపసమితుల మూలకాల మొత్తం మధ్య వ్యత్యాసాన్ని కనుగొనాలి మరియు అది గరిష్టంగా ఉండాలి. మేము a ను ఉపయోగించబోతున్నాము మ్యాప్. హ్యాషింగ్ ఈ ప్రశ్నను పరిష్కరించడానికి సమర్థవంతమైన మార్గాన్ని అందిస్తుంది. మేము రెండు మ్యాప్‌లను ఉపయోగించబోతున్నాము. ఒకటి సానుకూల అంశాలపై చేసిన ఆపరేషన్ల కోసం మరియు మరొకటి ప్రతికూల అంశాలపై. శ్రేణి సానుకూల మరియు ప్రతికూల అంశాలను రెండింటినీ కలిగి ఉంటుంది, కాబట్టి మనం కూడా ఆ విషయాన్ని నిర్వహించాలి.

మేము శ్రేణి మరియు మ్యాప్ తీసుకుంటాము. మేము శ్రేణి యొక్క ప్రతి మూలకాన్ని ఎంచుకుని, అది 0 కన్నా ఎక్కువ ఉందో లేదో తనిఖీ చేయబోతున్నాం. అప్పుడు మేము దానిని మ్యాప్‌లో దాని సంఘటనల సంఖ్యతో నిల్వ చేయబోతున్నాము. సానుకూల మూలకాల యొక్క పౌన encies పున్యాలను నిల్వ చేసిన తరువాత, మేము 0 కంటే ఎక్కువ మరియు 1 యొక్క పౌన frequency పున్యాన్ని కలిగి ఉన్న శ్రేణి యొక్క అన్ని విలువలను జోడించబోతున్నాము, అంటే ఒకటి కంటే ఎక్కువసార్లు లేదా అంతకంటే ఎక్కువ సార్లు వచ్చే మూలకాలను విస్మరించాలి.

అదే విషయం ప్రతికూల మూలకాలతో చేయబడుతుంది, మేము శ్రేణి యొక్క ప్రతి మూలకాన్ని ఎంచుకుంటాము మరియు ఈసారి అది 0 కన్నా తక్కువ ఉందో లేదో తనిఖీ చేస్తాము. మేము దానిని మ్యాప్‌లో నిల్వ చేయబోతున్నాము (ఇది సానుకూల సంఖ్యగా మారుతుంది) సంఘటనలు. ప్రతికూల మూలకాల యొక్క పౌన encies పున్యాలను నిల్వ చేసిన తరువాత, మేము 0 కంటే తక్కువ మరియు 1 యొక్క పౌన frequency పున్యాన్ని కలిగి ఉన్న శ్రేణి యొక్క అన్ని విలువలను జోడించబోతున్నాము. ఇక్కడ కూడా, మనం చాలాసార్లు లేదా అంతకంటే ఎక్కువ వచ్చే మూలకాలను విస్మరించాలి. ఒకసారి కంటే.

అన్ని పాజిటివ్ మరియు నెగటివ్ ఎలిమెంట్స్ కండిషన్ మొత్తాన్ని పొందిన తరువాత, ఫ్రీక్వెన్సీ 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

శ్రేణి యొక్క రెండు ఉపసమితుల గరిష్ట వ్యత్యాసాన్ని కనుగొనడానికి జావా కోడ్

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” శ్రేణిలోని మూలకాల సంఖ్య. మేము హాష్ మ్యాప్ ఉపయోగించినందున మేము O (1) లో చొప్పించడం / తొలగించడం / శోధించడం చేయగలము.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.