തന്നിരിക്കുന്ന രണ്ട് തരം അറേകളുടെ ഇതര ഘടകങ്ങളിൽ നിന്ന് സാധ്യമായ എല്ലാ അടുക്കിയ അറേകളും സൃഷ്ടിക്കുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഡയറക്റ്റി കാരാട്ട് പേപാൽ ട്വിలియో യാൻഡക്സ്
അറേ റിക്കറിഷൻ

“രണ്ട് അടുക്കിയ അറേകളുടെ ഇതര ഘടകങ്ങളിൽ നിന്ന് സാധ്യമായ എല്ലാ തരംതിരിച്ച അറേകളും സൃഷ്ടിക്കുക” എന്ന പ്രശ്നം, നിങ്ങൾക്ക് രണ്ട് അടുക്കിയ അറേകളുണ്ടെന്ന് കരുതുക. നൽകിയിട്ടുള്ള രണ്ട് വ്യത്യസ്ത അറേകളിൽ നിന്ന് പകരമായി ക്രമീകരിക്കേണ്ട തരത്തിലുള്ള അടുക്കിയ അറേകൾ കണ്ടെത്താൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

ഉദാഹരണം  

ArrA[] = {9, 12, 66}
ArrB[] = {10, 15, 25}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

വിശദീകരണം

എല്ലാ ഇതര സംഖ്യകളും വ്യത്യസ്ത അറേകളിൽ നിന്നുള്ളതും അടുക്കിയതുമാണ്.

തന്നിരിക്കുന്ന രണ്ട് തരം അറേകളുടെ ഇതര ഘടകങ്ങളിൽ നിന്ന് സാധ്യമായ എല്ലാ അടുക്കിയ അറേകളും സൃഷ്ടിക്കുക

 

അൽഗോരിതം  

  1. വലുപ്പത്തിന്റെ output ട്ട്‌പുട്ട് അറേ പ്രഖ്യാപിക്കുക m + n (രണ്ട് അറേകളുടെയും ദൈർഘ്യം).
  2. പരിശോധിക്കുക boolCondition സത്യമാണ്,
    1. The ട്ട്‌പുട്ട് അറേയുടെ ദൈർഘ്യം 0 ന് തുല്യമല്ലേ എന്ന് പരിശോധിക്കുക, തുടർന്ന് output ട്ട്‌പുട്ട് അറേ പ്രിന്റുചെയ്യുക.
      1. അറേയിലൂടെ സഞ്ചരിക്കുക അറ ഇനിപ്പറയുന്നവ പരിശോധിക്കുക
        1. Ar ട്ട്‌പുട്ട് അറേയുടെ ദൈർഘ്യം 0 ആണെങ്കിൽ, element ട്ട്‌പുട്ട് അറേയിലേക്ക് നിലവിലെ ഘടകം പകർത്തുക, തുടർന്ന് ആവർത്തിച്ച് ഫംഗ്ഷനെ വിളിക്കുക.
    2. നിലവിലെ അറേ ഘടകം മുമ്പത്തെ output ട്ട്‌പുട്ട് അറേ ഘടകത്തേക്കാൾ വലുതാണെങ്കിൽ, അതിൽ നിന്ന് ഘടകം പകർത്തുക അറ the ട്ട്‌പുട്ട് അറേയിലേക്ക് പോയി ഫംഗ്ഷനെ ആവർത്തിച്ച് വിളിക്കുക.
  3. ബൂൾ കണ്ടീഷൻ തെറ്റാണെങ്കിൽ, അതിലൂടെ സഞ്ചരിക്കുക ആർബി ന്റെ നിലവിലെ ഘടകം ഉണ്ടോയെന്ന് പരിശോധിക്കുക ആർബി the ട്ട്‌പുട്ട് അറേയുടെ നിലവിലെ ഘടകത്തേക്കാൾ വലുതാണ്
      1. ശരിയാണെങ്കിൽ ഘടകം ഇതിൽ നിന്ന് പകർത്തുക ആർബി the ട്ട്‌പുട്ട് അറേയിലേക്ക് പോയി ഫംഗ്ഷനെ ആവർത്തിച്ച് വിളിക്കുക.
ഇതും കാണുക
തന്നിരിക്കുന്ന രണ്ട് സെറ്റുകൾ ഡിജോയിറ്റ് ആണോ എന്ന് എങ്ങനെ പരിശോധിക്കും?

വിശദീകരണം

“തന്നിരിക്കുന്ന രണ്ട് തരം അറേകളുടെ ഇതര ഘടകങ്ങളിൽ നിന്ന് സാധ്യമായ എല്ലാ തരംതിരിച്ച അറേകളും സൃഷ്ടിക്കുക” എന്ന പ്രശ്നം ഇനിപ്പറയുന്ന രീതിയിൽ പരിഹരിക്കാൻ കഴിയും. ഇവിടെ നമുക്ക് രണ്ട് അടുക്കിയ അറേകൾ നൽകിയിരിക്കുന്നു അറ ഒപ്പം ആർബി. നൽകിയിരിക്കുന്ന രണ്ട് അറേകളും അടുക്കിയ ക്രമത്തിലാണ്. അതിനാൽ, സാധ്യമായതെല്ലാം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട് ശ്രേണികൾ അവ അടുക്കിയ രീതിയിൽ നിർമ്മിക്കാൻ കഴിയും. Condition ട്ട്‌പുട്ടിലെ ഓരോ ഇതര ഘടകങ്ങളും വ്യത്യസ്ത അറേകളിൽ നിന്ന് വരണം എന്ന മറ്റൊരു വ്യവസ്ഥയുമുണ്ട്.

സാധ്യമായ എല്ലാ output ട്ട്‌പുട്ട് അറേകളും കണ്ടെത്തുന്നതിന് ഞങ്ങൾ ആ ഫംഗ്ഷനെ ആവർത്തിച്ച് വിളിക്കും. തിരഞ്ഞെടുക്കേണ്ട ഘടകങ്ങളുടെ ട്രാക്ക് സൂക്ഷിക്കുന്ന ഒരു ബൂലിയൻ വേരിയബിൾ ഞങ്ങൾ സൂക്ഷിക്കുന്നു. അത് ഒന്നുകിൽ നിലവിലെ ArrA അല്ലെങ്കിൽ ArrB- ൽ നിന്നുള്ളതാണ്. ബൂളിയൻ വേരിയബിൾ ശരിയാണെങ്കിൽ, ആദ്യത്തെ അറേ അറയിൽ നിന്ന് ഞങ്ങൾ ഒരു ഘടകം തിരഞ്ഞെടുക്കുന്നു. അല്ലാത്തപക്ഷം ബൂളിയൻ വേരിയബിൾ തെറ്റാണെങ്കിൽ, രണ്ടാമത്തെ അറേ ArrB യിൽ നിന്ന് ഞങ്ങൾ ഘടകം തിരഞ്ഞെടുക്കുന്നു. ബൂളിയൻ വേരിയബിൾ ശരിയാണെങ്കിൽ, അറേയുടെ നീളം 0 ന് തുല്യമോ 0 നേക്കാൾ വലുതോ ആണോ എന്ന് പരിശോധിക്കാൻ പോകുന്നു, ഓരോ തവണയും ഞങ്ങൾ output ട്ട്‌പുട്ട് അറേ പ്രിന്റുചെയ്യാൻ പോകുന്നു.

ബൂളിയൻ അവസ്ഥ ശരിയാണെങ്കിൽ‌ ഞങ്ങൾ‌ അറേ അറേയിലൂടെ സഞ്ചരിക്കാൻ‌ പോകുന്നു. നിലവിലെ അറേ ഘടകം output ട്ട്‌പുട്ട് അറേയിലേക്ക് പകർത്തുക. ആവശ്യമായ എല്ലാ ആർഗ്യുമെന്റുകളും കൈമാറുന്ന ഫംഗ്ഷനെ ഞങ്ങൾ ആവർത്തിച്ച് വിളിക്കുന്നു. ബൂളിയൻ അവസ്ഥ തെറ്റാണെങ്കിൽ. ഞങ്ങളുടെ output ട്ട്‌പുട്ട് അറേയിൽ നിന്ന് പകർത്താനും അപ്‌ഡേറ്റുചെയ്യാനും ഞങ്ങൾ ArrB ഉപയോഗിക്കുന്നു. Output ട്ട്‌പുട്ട് അറേയുടെ ദൈർഘ്യം 0 ആകുമ്പോഴെല്ലാം, അറേ പ്രിന്റുചെയ്യുക.

ഇതും കാണുക
പരമാവധി ഉൽപ്പന്ന സബ്‌റേ

കോഡ്  

സാധ്യമായ എല്ലാ അടുക്കിയ അറേകളും സൃഷ്ടിക്കുന്നതിനുള്ള സി ++ കോഡ്

#include<iostream>
using namespace std;

void printArray(int arr[], int n);

void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, bool flag)
{
    if (flag)
    {
        if (len)
            printArray(output, len+1);

        for (int k = i; k < m; k++)
        {
            if (!len)
            {
                output[len] = ArrA [k];
                getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
            }
            else
            {
                if (ArrA [k] > output[len])
                {
                    output[len+1] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                }
            }
        }
    }
    else
    {
        for (int l = j; l < n; l++)
        {
            if (ArrB[l] > output[len])
            {
                output[len+1] = ArrB[l];
                getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
            }
        }
    }
}

void generate(int ArrA [], int ArrB[], int m, int n)
{
    int output[m+n];
    getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    int ArrA [] = {9, 12, 66};
    int ArrB[] = {10, 15, 25};
    int n = sizeof(ArrA)/sizeof(ArrA [0]);
    int m = sizeof(ArrB)/sizeof(ArrB[0]);
    generate(ArrA, ArrB, n, m);
    return 0;
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

സാധ്യമായ എല്ലാ അടുക്കിയ അറേകളും സൃഷ്ടിക്കുന്നതിനുള്ള ജാവ കോഡ്

class GeneratedSortedArray
{
    public static void getSortedArr(int ArrA[], int ArrB[], int output[], int i, int j, int m, int n, int len, boolean flag)
    {
        if (flag)
        {
            if (len!=0)
                printArray(output, len+1);

            for (int k = i; k < m; k++)
            {
                if (len==0)
                {
                    output[len] = ArrA [k];
                    getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len, !flag);
                }
                else
                {
                    if (ArrA [k] > output[len])
                    {
                        output[len+1] = ArrA [k];
                        getSortedArr(ArrA, ArrB, output, k+1, j, m, n, len+1, !flag);
                    }
                }
            }
        }
        else
        {
            for (int l = j; l < n; l++)
            {
                if (ArrB[l] > output[len])
                {
                    output[len+1] = ArrB[l];
                    getSortedArr(ArrA, ArrB, output, i, l+1, m, n, len+1, !flag);
                }
            }
        }
    }

    public static void generate(int ArrA [], int ArrB[], int m, int n)
    {
        int output[]=new int[m+n];
        getSortedArr(ArrA, ArrB, output, 0, 0, m, n, 0, true);
    }
    
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
    public static void main(String [] args)
    {
        int ArrA [] = {9, 12, 66};
        int ArrB[] = {10, 15, 25};
        int n = ArrA.length;
        int m = ArrB.length;
        generate(ArrA, ArrB, n, m);
    }
}
9 10
9 10 12 15
9 10 12 25
9 15
9 25
12 15
12 25

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (n1 ^ 2 + n2 ^ 2) എവിടെ “N1” ഒപ്പം “N2” ArrA, ArrB എന്നിവയുടെ നീളം. ഘടകങ്ങൾ ഒന്നിടവിട്ട് മാറുമ്പോൾ, അതാണ് ArrA [0] <ArrB [0] <ArrA [1] <ArrB [1]… ഈ സാഹചര്യത്തിൽ, നമുക്ക് ആകെ n1 ^ 2 + n2 ^ 2 സാധ്യമായ ഉപസെറ്റുകൾ ഉണ്ടായിരിക്കാം. അങ്ങനെ ഒരു പോളിനോമിയൽ സമയ സങ്കീർണ്ണത.

ഇതും കാണുക
വിരളമായ പട്ടിക ഉപയോഗിച്ച് ശ്രേണി തുക അന്വേഷണം

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

O (n1 + n2) എവിടെ “N1” ഒപ്പം “N2” ArrA, ArrB എന്നിവയുടെ നീളം. Space ട്ട്‌പുട്ട് അറേയാണ് സ്പേസ് എടുക്കുന്നത്, വലുപ്പം n1 + n2 ആയതിനാൽ. സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.