എപി രൂപപ്പെടുന്ന അടുക്കിയ അറേയിൽ എല്ലാ ത്രിവർണ്ണങ്ങളും അച്ചടിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് അക്കോലൈറ്റ് കഡെൻസ് ഇന്ത്യ ഗൂഗിൾ വിവരം Intuit പോസ്റ്റ്
അറേ ഹാഷ് തിരയുന്നു

“എപി രൂപപ്പെടുന്ന എല്ലാ ത്രിവർണ്ണങ്ങളും അടുക്കിയ അറേയിൽ അച്ചടിക്കുക” എന്ന പ്രശ്നം ഞങ്ങൾ ഒരു അടുക്കിയതാണെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ അറേ. ഒരു ഗണിത പുരോഗതിക്ക് സാധ്യമായ എല്ലാ ത്രിമൂർത്തികളും കണ്ടെത്തുക എന്നതാണ് ചുമതല.

എപി രൂപപ്പെടുന്ന അടുക്കിയ അറേയിൽ എല്ലാ ത്രിവർണ്ണങ്ങളും അച്ചടിക്കുക

ഉദാഹരണം

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

വിശദീകരണം

ഇവയെല്ലാം ഒരു എ.പി.

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

വിശദീകരണം

ഇവയെല്ലാം ഒരു എ.പി.

അൽഗോരിതം

  1. നിന്ന് ലൂപ്പ് i = 1 മുതൽ n-1 വരെ(ഉൾപ്പെടുത്തിയിട്ടില്ല).
  2. J ന്റെ മൂല്യം i യേക്കാൾ കുറവായും k ന്റെ മൂല്യം i നേക്കാൾ ഒന്നായും സജ്ജമാക്കുക.
  3. അതേസമയം j> = 0 && k <n.
    1. നിലവിലെ രണ്ട് അറേ ഘടകങ്ങളുടെ ആകെത്തുക മറ്റ് അറേ ഘടകത്തിന്റെ ഇരട്ടിക്ക് തുല്യമാണോയെന്ന് പരിശോധിക്കുക,
      1. ശരിയാണെങ്കിൽ, നിലവിലെ മൂന്ന് ഘടകങ്ങൾ അച്ചടിച്ച് യഥാക്രമം k, j എന്നിവയുടെ മൂല്യം കുറയ്ക്കുകയും വർദ്ധിപ്പിക്കുകയും ചെയ്യുക.
    2. രണ്ട് മൂലകങ്ങളുടെ ആകെത്തുക മറ്റൊരു മൂലകത്തിന്റെ ഇരട്ടിയിൽ കുറവാണോയെന്ന് പരിശോധിക്കുക, തുടർന്ന്, കെ 1 വർദ്ധിപ്പിക്കുക.
    3. രണ്ട് മൂലകങ്ങളുടെ ആകെത്തുക മറ്റൊരു മൂലകത്തിന്റെ ഇരട്ടിയിലധികം വലുതാണോയെന്ന് പരിശോധിക്കുക, തുടർന്ന്, j 1 ആയി കുറയ്ക്കുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു നൽകി അടുക്കി ശ്രേണി. ഒരു ഗണിത പുരോഗതിക്ക് കാരണമാകുന്ന എല്ലാ ത്രിമൂർത്തികളും കണ്ടെത്താൻ ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. ഒരു ഗണിത പുരോഗതിയെ ഒരു സംഖ്യയായി നിർവചിക്കാം, അതിൽ എല്ലാ മൂലകങ്ങളും തുടർച്ചയായി വരുന്ന ശ്രേണിയിൽ ഒരു പ്രത്യേക അകലം മുഴുവൻ വരുന്നു. ഒരു + സി = 2 ബി എന്ന് പറയുന്ന ഒരു എപിയുടെ സൂത്രവാക്യം ഉപയോഗിച്ച് ഞങ്ങൾ ട്രിപ്പിൾ കണ്ടെത്തും, അതായത് രണ്ട് അക്കങ്ങളുടെ ആകെത്തുക മൂന്നാമത്തെ സംഖ്യയുടെ ഇരട്ടിക്ക് തുല്യമാണെങ്കിൽ.

ലൂപ്പിനും a നും ഒരെണ്ണം ഉപയോഗിച്ച് മുഴുവൻ അറേയും സഞ്ചരിക്കുക ലൂപ്പ് സമയത്ത്, 'അതേസമയം ലൂപ്പ്' മൂന്ന് ഘടകങ്ങൾക്ക് എപി രൂപീകരിക്കാൻ കഴിയുമോ ഇല്ലയോ എന്ന് പരിശോധിക്കാൻ പോകുന്നു. ഫോർ ലൂപ്പിലൂടെ സഞ്ചരിക്കുമ്പോഴെല്ലാം j യുടെ മൂല്യം i യുടെ മൂല്യത്തേക്കാൾ കുറവും k യുടെ മൂല്യം i യുടെ മൂല്യത്തേക്കാൾ ഒന്നുമായി സജ്ജമാക്കും. ഇത് ഞങ്ങൾക്ക് പരിശോധിക്കുന്നതിനായി ഒരു ഘടകം എടുക്കും, അതിനാൽ ഓരോ തവണയും നമുക്ക് ar [i], arr [j], arr [k] എന്നിവ പരിശോധിക്കാൻ മൂന്ന് ഘടകങ്ങൾ ഉള്ളപ്പോൾ, ഓരോന്നിനും വ്യത്യാസപ്പെടുന്ന i, j, k എന്നിവയുടെ മൂല്യം ലൂപ്പിലായാലും അല്ലാതെയായാലും സഞ്ചരിക്കുക ലൂപ്പ് സമയത്ത്.

രണ്ട് ഘടകങ്ങളുടെ ആകെത്തുക മൂന്നാമത്തെ ഘടകത്തിന് തുല്യമാണെന്ന് ഞങ്ങൾ കണ്ടെത്തിയാൽ, ഞങ്ങൾ ആ മൂന്ന് അറേ ഘടകങ്ങളും അച്ചടിക്കാൻ പോകുന്നു, അവയ്ക്ക് ഒരു എപി രൂപീകരിക്കാൻ കഴിയും. ഞങ്ങളുടെ അൽ‌ഗോരിതം അനുസരിച്ച് j, k എന്നിവയുടെ മൂല്യം ഞങ്ങൾ അപ്‌ഡേറ്റ് ചെയ്യും. മൂന്നാമത്തെ മൂലകത്തിന്റെ ഇരട്ടിയിൽ താഴെയുള്ള രണ്ട് മൂലകങ്ങളുടെ ആകെത്തുക ഞങ്ങൾ കണ്ടെത്തിയാൽ. K യുടെ മൂല്യം ഞങ്ങൾ വർദ്ധിപ്പിക്കും, അല്ലെങ്കിൽ മൂന്നാമത്തെ മൂലകത്തിന്റെ ഇരട്ടിയിലധികം തുക കണ്ടെത്തിയാൽ, j യുടെ മൂല്യം കുറയ്ക്കും. മുഴുവൻ അറേയിലും സഞ്ചരിച്ച് ഒരു എപി രൂപീകരിക്കാൻ സാധ്യതയുള്ള എല്ലാ ഘടകങ്ങളും കണ്ടെത്തുന്നതുവരെ ഇത് തുടരും.

കോഡ്

എപി രൂപപ്പെടുന്ന അടുക്കിയ അറേയിൽ എല്ലാ മൂന്നും പ്രിന്റുചെയ്യാനുള്ള സി ++ കോഡ്

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

ജാവാ കോഡ് എപി രൂപപ്പെടുന്ന എല്ലാ ത്രിവർണ്ണങ്ങളും അടുക്കിയ അറേയിൽ അച്ചടിക്കുക

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

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

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

O (n2എവിടെ “N”  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾക്ക് രണ്ട് നെസ്റ്റഡ് ലൂപ്പ് ഉണ്ട്, അവിടെ ആദ്യത്തെ ലൂപ്പ് അവസാനം എത്തുന്നതുവരെ പ്രവർത്തിക്കുന്നു, തുടർന്ന് രണ്ടാമത്തെ നെസ്റ്റഡ് ലൂപ്പ് എപിയുടെ ഘടകങ്ങൾ കണ്ടെത്താൻ ഉപയോഗിക്കുന്നു.

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

O (1) അധിക ഇടം ആവശ്യമില്ലാത്തതിനാൽ.