പൂജ്യം തുക ഉപയോഗിച്ച് എല്ലാ മൂന്നും കണ്ടെത്തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ GE ഹെൽത്ത്കെയർ ഗൂഗിൾ ഉയർത്തൽ
അറേ ഹാഷ് തിരയുന്നു ക്രമപ്പെടുത്തൽ

“പൂജ്യ സംഖ്യയുള്ള എല്ലാ ത്രിമൂർത്തികളെയും കണ്ടെത്തുക” എന്ന പ്രശ്‌നം, നിങ്ങൾക്ക് പോസിറ്റീവ്, നെഗറ്റീവ് സംഖ്യ അടങ്ങിയ ഒരു അറേ നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. 0 ന് തുല്യമായ തുകയുള്ള ട്രിപ്പിൾ കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു.

പൂജ്യം തുക ഉപയോഗിച്ച് എല്ലാ മൂന്നും കണ്ടെത്തുക

ഉദാഹരണം

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

വിശദീകരണം

ഇവയുടെ ആകെത്തുക 0 എന്ന മൂന്നിരട്ടിയാണ്.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

വിശദീകരണം

സംഖ്യകളുടെ സംഖ്യ 0 ⇒ -5 + 2 + 3 = 0 എന്ന മൂന്നിരട്ടികളാണ് ഇവ

അൽഗോരിതം

  1. അടുക്കുക നൽകിയ അറേ.
  2. സജ്ജമാക്കുക ബൂളിയൻ വേരിയബിൾ കണ്ടുപിടിച്ചു തെറ്റിലേക്ക്.
  3. I = 0 മുതൽ i വരെ ലൂപ്പുചെയ്യുന്നു
    1. ഗണം fir = i + 1, sec = n-1 മറ്റൊരു വേരിയബിൾ x നിലവിലെ അറേ ഘടകത്തിലേക്ക്.
    2. സരള സമയത്ത്
      1. മൂന്ന് ഘടകങ്ങളും ഒരുമിച്ച് 0 ആകുന്നുണ്ടോയെന്ന് പരിശോധിക്കുക.
        1. ശരിയാണെങ്കിൽ, മൂന്ന് നമ്പറുകളും പ്രിന്റുചെയ്‌ത് isFound to true എന്ന് സജ്ജമാക്കുക.
      2. മൂന്ന് ഘടകങ്ങളുടെ (നിലവിലെ അറേ ഘടകങ്ങൾ) ആകെത്തുക 0 ൽ കുറവാണോയെന്ന് പരിശോധിക്കുക.
        1. ശരിയാണെങ്കിൽ, fir ന്റെ മൂല്യം 1 വർദ്ധിപ്പിക്കുക.
      3. മൂന്ന് ഘടകങ്ങളുടെ ആകെത്തുക 0 നേക്കാൾ വലുതാണോയെന്ന് പരിശോധിക്കുക.
          1. ശരിയാണെങ്കിൽ, സെക്കന്റിന്റെ മൂല്യം 1 കുറയ്ക്കുക.
  4. IsFound തെറ്റാണോയെന്ന് പരിശോധിക്കുക, അതിനർത്ഥം ത്രിമൂർത്തികളൊന്നും രൂപീകരിക്കാൻ കഴിയില്ല.

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു ശ്രേണി നൽകിയിരിക്കുന്നു. തന്നിരിക്കുന്ന സംഖ്യകൾക്കൊപ്പം ഒരു അറേയിൽ ആകാവുന്ന സംഖ്യകൾ 0 ആയി നിർണ്ണയിക്കാൻ ഞങ്ങൾ ആവശ്യപ്പെടുന്നു. ഞങ്ങൾ ഒരു നെസ്റ്റഡ് ലൂപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു. ഈ അൽ‌ഗോരിതം സ്ഥിരമായ സ്ഥലത്ത് പ്രവർത്തിക്കാൻ‌ കഴിയും. ആദ്യം, ഞങ്ങൾ അറേ അടുക്കാൻ പോകുന്നു. ഇതുവഴി നമുക്ക് രണ്ട് പോയിന്റർ സാങ്കേതികത ഉപയോഗിക്കാം. ഞങ്ങൾ ആദ്യം ഒരു ബൂളിയൻ വേരിയബിൾ പ്രഖ്യാപിക്കുകയും അതിന്റെ മൂല്യം ആദ്യം തെറ്റായി സജ്ജമാക്കുകയും ചെയ്യും. മൂലകങ്ങളുടെ ആകെത്തുക 0 എന്ന മൂല്യമുള്ള ത്രിവർണ്ണങ്ങളൊന്നും ഞങ്ങൾ കണ്ടെത്തിയില്ലെന്ന് ഉറപ്പാക്കാനാണിത് കണ്ടുപിടിച്ചു തെറ്റായി അവശേഷിക്കുന്നു. ഒരു ട്രിപ്പിൾ കണ്ടെത്തുമ്പോഴെല്ലാം ഞങ്ങൾ അത് ട്രൂ ആയി അപ്‌ഡേറ്റ് ചെയ്യാൻ പോകുന്നു. അതിനാൽ, ത്രിമൂർത്തികളൊന്നും കണ്ടെത്തിയില്ലെന്ന് നമുക്ക് നിഗമനം ചെയ്യാം.

നെസ്റ്റഡ് ലൂപ്പിൽ ഞങ്ങൾ ആദ്യം അറേ അടുക്കും. തുടർന്ന് നമ്മൾ n-1 വരെ അറേയിലൂടെ സഞ്ചരിക്കുന്നു. ആരംഭ മൂല്യം i + 1, അവസാന മൂല്യം n-1, x എന്നിവ ബാഹ്യ ലൂപ്പിലെ നിലവിലെ മൂല്യത്തിലേക്ക് സജ്ജമാക്കും. ആന്തരിക ലൂപ്പിൽ ഞങ്ങൾ ഒരു അറേയുടെ മൂല്യങ്ങൾ സഞ്ചരിക്കും, കൂടാതെ മൂന്ന് മൂലകങ്ങളുടെയും (x + arr [fir] + arr [sec]) ആകെത്തുക 0 ന് തുല്യമാണോ എന്ന് പരിശോധിക്കും. ഇത് 0 ആണെന്ന് കണ്ടെത്തിയാൽ, അതിനർത്ഥം ഞങ്ങൾ ആദ്യ ജോഡി കണ്ടെത്തി ഒരു അറേയുടെ നിലവിലെ എല്ലാ മൂല്യങ്ങളും പ്രിന്റുചെയ്‌ത്, isFound മൂല്യം true എന്ന് സജ്ജമാക്കുക.

ജോഡികളിലൊന്ന് ഞങ്ങൾ കണ്ടെത്തിയെന്ന് ഇത് സൂചിപ്പിക്കുന്നു. ട്രിപ്പിളിന്റെ ആകെത്തുക 0 ന് തുല്യമല്ലെങ്കിൽ, നിലവിലെ മൂന്ന് മൂലകങ്ങളുടെ ആകെത്തുക 0 ൽ കുറവാണോ എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. തുക 0 ൽ കുറവാണെങ്കിൽ ഞങ്ങൾ ഫിർ വർദ്ധിപ്പിക്കുന്നു, അതിനർത്ഥം ഞങ്ങളുടെ ആരംഭ മൂല്യം വർദ്ധിച്ചു എന്നാണ്. അവസ്ഥ തൃപ്‌തികരമല്ലെങ്കിൽ. തുക 0 നേക്കാൾ വലുതാണോയെന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. ശരിയാണെങ്കിൽ, സെക്കന്റ് കുറയ്ക്കുക.

ഈ രീതിയിൽ, 0 ആയി കണക്കാക്കാവുന്ന സാധ്യമായ എല്ലാ ത്രിമൂർത്തികളും ഞങ്ങൾ കണ്ടെത്താൻ പോകുന്നു.

പൂജ്യം ആകെ എല്ലാ ട്രിപ്പിളുകളും കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

പൂജ്യം തുക ഉപയോഗിച്ച് എല്ലാ മൂന്നും കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

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

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

O (n2) എവിടെ “N”  അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. O (n) സമയത്തിനായി സംഭാവന ചെയ്യുന്ന രണ്ട് പോയിന്റർ സാങ്കേതികത ഞങ്ങൾ ഉപയോഗിക്കുന്നതിനാൽ. എന്നാൽ ഈ സാങ്കേതികവിദ്യ O (n) സമയത്തിനായി ഉപയോഗിക്കുന്നു. അങ്ങനെ അൽ‌ഗോരിതം O (n ^ 2) സമയത്ത് പ്രവർത്തിക്കുന്നു.

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

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