ഒരു അറേയുടെ രണ്ട് ഉപസെറ്റുകളുടെ പരമാവധി വ്യത്യാസം


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു അത്ലഷിഅന് കഡെൻസ് ഇന്ത്യ ഡയറക്റ്റി ഫ്രീചാർജ് Opera പേ 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 മാത്രം ആവൃത്തിയിലുള്ളതുമായ ഒരു അറേയുടെ എല്ലാ മൂല്യങ്ങളും ഞങ്ങൾ ചേർക്കാൻ പോകുന്നു. ഇവിടെയും, നിരവധി തവണയോ അതിൽ കൂടുതലോ വരുന്ന ഘടകങ്ങളെ അവഗണിക്കേണ്ടതുണ്ട്. ഒന്നിലധികം തവണ.

എല്ലാ പോസിറ്റീവ്, നെഗറ്റീവ് മൂലകങ്ങളുടെയും ആകെത്തുക ലഭിച്ചതിനുശേഷം, ഫ്രീക്വൻസി 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) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ O (1) ൽ ഉൾപ്പെടുത്തൽ / ഇല്ലാതാക്കൽ / തിരയൽ നടത്താൻ ഞങ്ങൾക്ക് കഴിയും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.