നൽകിയ ഉൽപ്പന്നവുമായി ജോടിയാക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു 24 * 7 ഇന്നൊവേഷൻ ലാബുകൾ ആമസോൺ അവലാര Quora Roblox
അറേ ഹാഷ് മഠം

“തന്നിരിക്കുന്ന ഉൽപ്പന്നവുമായി ജോടിയാക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി കൂടാതെ “x” എന്ന സംഖ്യയും. തന്നിരിക്കുന്ന ഇൻപുട്ട് അറേയിൽ 'x' എന്നതിന് തുല്യമായ ഉൽപ്പന്നത്തിന്റെ ഒരു ജോഡി ഒരു അറേയിൽ അടങ്ങിയിട്ടുണ്ടോ എന്ന് നിർണ്ണയിക്കുക.

ഉദാഹരണം

[2,30,12,5]
x = 10
Yes, it has Product Pair

വിശദീകരണം

നൽകിയ ഉൽപ്പന്നവുമായി ജോടിയാക്കുക

ഇവിടെ 2 ഉം 5 ഉം ഉൽ‌പന്നം 10 അതായത് x ന് തുല്യമാണ്.

[10,30,12,50]
x = 40
No, it does not have a Product Pair.

വിശദീകരണം

അറേയിൽ അത്തരമൊരു ജോഡി ഇല്ല, അതിന്റെ ഉൽപ്പന്നം x അതായത് 40 ന് തുല്യമാണ്.

[20,3,12,5]
x = 100
Yes, it has a Product Pair.

വിശദീകരണം

ഇവിടെ അറേയിലെ 20 ഉം 5 ഉം ഒരു ജോഡിയായി മാറുന്നു, അതിന്റെ ഉൽപ്പന്നം x അതായത് 100 ന് തുല്യമാണ്.

തന്നിരിക്കുന്ന ഉൽപ്പന്നവുമായി ജോടിയുണ്ടോയെന്ന് കണ്ടെത്താനുള്ള അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഹാഷ്‌സെറ്റ്.
  2. കുറഞ്ഞത് 2 മൂല്യങ്ങളെങ്കിലും നൽകിയിട്ടുണ്ടെങ്കിൽ അറേയുടെ ദൈർഘ്യം പരിശോധിക്കുക.
    1. ഇല്ലെങ്കിൽ, തെറ്റായി മടങ്ങുക.
  3. അതേസമയം i <n.
    1. അറേയിലെ ഘടകങ്ങളിലൊന്ന് 0 ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക
      1. X- നും 0 നൽകിയിട്ടുണ്ടെങ്കിൽ, true ആയി മടങ്ങുക.
    2. X- നെ അറയുടെ ഏതെങ്കിലും മൂലകങ്ങളാൽ വിഭജിച്ച് ബാക്കിയുള്ള 0 നൽകുന്നുണ്ടോയെന്ന് പരിശോധിക്കുക.
      1. ഹാഷ്‌സെറ്റിൽ (x / arr [i]) അടങ്ങിയിട്ടുണ്ടെങ്കിൽ, ശരിയിലേക്ക് മടങ്ങുക.
      2. ഹാഷ്‌സെറ്റിലേക്ക് arr [i] ചേർക്കുക.
  4. തെറ്റായി മടങ്ങുക.

വിശദീകരണം

ഒരു അറേയും ഒരു നമ്പറും നൽകുന്ന ഒരു പ്രശ്നം ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. X- ന് തുല്യമായ ഒരു ഉൽപ്പന്നമുള്ള ഇൻപുട്ട് അറേയിൽ ഏതെങ്കിലും ജോഡി നിലവിലുണ്ടോ എന്ന് ഞങ്ങൾ കണ്ടെത്തണം. ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ് ഈ പ്രശ്നം പരിഹരിക്കാൻ. തന്നിരിക്കുന്ന ഉൽ‌പ്പന്നത്തിനൊപ്പം ഒരു അറേയിൽ‌ നിലനിൽക്കുന്ന മൂല്യം കണ്ടെത്തുന്നതിന്. X നെ arr [i] ഉപയോഗിച്ച് വിഭജിച്ച് ബാക്കി 0 ആണോ എന്ന് പരിശോധിക്കുന്നു. 0 ആണെന്ന് കണ്ടെത്തിയാൽ x / arr [i] ഹാഷ്‌സെറ്റിൽ ഉണ്ടോ എന്ന് പരിശോധിക്കും. അത് നിലവിലുണ്ടെങ്കിൽ ഞങ്ങൾ ശരിയാകും. ഇല്ലെങ്കിൽ, കൂടുതൽ സഞ്ചരിക്കാനായി ആ ഘടക ശ്രേണി ഹാഷ്‌സെറ്റിലേക്ക് ചേർക്കുക.

ഉൽപ്പന്നം പൂജ്യം വ്യക്തമായി പരിശോധിക്കുന്നതിനുള്ള ഒരു വ്യവസ്ഥയും ഞങ്ങൾക്ക് നൽകിയിട്ടുണ്ട്. ഞങ്ങളുടെ x മൂല്യം 0 ആയി നൽകിയിട്ടുണ്ടെങ്കിൽ, അറേയിലെ ഏതെങ്കിലും ഘടകങ്ങൾ 0 ആണോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും. അങ്ങനെയാണെങ്കിൽ, നമ്മൾ ശരിയാണ്, കാരണം പൂജ്യം എന്തിനാലും ഗുണിച്ചാൽ എല്ലായ്പ്പോഴും പൂജ്യമായിരിക്കും.

നമുക്ക് ഒരു ഉദാഹരണം എടുത്ത് ഇത് മനസിലാക്കാം:

arr [] = {10,20,9,40}, X = 90

i = 0, arr [i] = 10,

Ar [i] 0 ന് തുല്യമാണോയെന്ന് ഞങ്ങൾ പരിശോധിക്കും, എന്നാൽ ഈ അറേയിൽ ഒരു ഘടകം പോലും 0 അല്ല, അതിനാൽ ഇത് ഒരു ആവർത്തനത്തിലും പ്രവർത്തിക്കില്ല.

X% arr [i] = = 0 അത് കടന്നുപോകുന്നുണ്ടോ എന്ന് ഞങ്ങൾ ഇവിടെ പരിശോധിക്കും, തുടർന്ന് x / arr [i] സജ്ജമാണോ എന്ന് പരിശോധിക്കും.

90% 10 == 0 ശരിയാണ്, 90/10 = 9 ഇതുവരെ ഒരു ഹാഷ്‌സെറ്റിൽ ഇല്ല.

അതിനാൽ ഞങ്ങൾ arr [i] = 10 സെറ്റിലേക്ക് ചേർക്കും.

90% 20 == 0 തെറ്റാണ്, ഒന്നും സംഭവിക്കുന്നില്ല

90% 9 == 0 ശരിയാണ്, 90/9 = 10 ഞങ്ങൾ ഇതിനകം ഒരു ഹാഷ്‌സെറ്റിൽ ചേർത്തിട്ടുള്ളതുപോലെ ഒരു ഹാഷ്‌സെറ്റിൽ ഉണ്ട്.

അതിനാൽ, ഒരു അറേയിൽ 9, 10 എന്നിങ്ങനെ ഒരു ഉൽപ്പന്ന ജോഡി ഞങ്ങൾക്ക് ഉണ്ടെന്നും അത് ശരിയാക്കി പ്രിന്റുചെയ്യുന്നുവെന്നും അർത്ഥമാക്കുന്നു

Put ട്ട്‌പുട്ട്: “അതെ, ഇതിന് ഉൽപ്പന്ന ജോടിയുണ്ട്”.

തന്നിരിക്കുന്ന ഉൽപ്പന്ന അമാസോണിനൊപ്പം ജോഡി കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#include<iostream>
#include<unordered_set>
using namespace std;
bool getProduct (int arr[], int n, int x)
{
  if (n < 2)
    return false;

  unordered_set<int> s;

  for (int i=0; i<n; i++)
  {
    if (arr[i] == 0)
    {
    if (x == 0)
      return true;
    else
      continue;
    }
    if (x%arr[i] == 0)
    {
      if (s.find(x/arr[i]) != s.end())
                return true;

      s.insert(arr[i]);
    }
  }
  return false;
}
int main()
{
  int arr[] = {10, 20, 9, 40};
  int x = 90;
  int n = sizeof(arr)/sizeof(arr[0]);
  getProduct (arr, n, x)? cout << "Yes, it has Product Pair\n":cout << "No, it does not have Product Pair";
  return 0;
}
Yes, it has Product Pair

തന്നിരിക്കുന്ന ഉൽപ്പന്നവുമായി ജോടിയാക്കാനുള്ള ജാവ കോഡ്

import java.util.HashSet;

class pairX
{
    public static boolean getProduct (int arr[], int n, int x)
    {
        HashSet<Integer> mySet = new HashSet<>();

        if(n < 2)
            return false;

        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
            {
                if(x == 0)
                    return true;
                else
                    continue;
            }
            if(x % arr[i] == 0)
            {
                if(mySet.contains(x / arr[i]))
                    return true;

                mySet.add(arr[i]);
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 9, 40};
        int x = 90;
        int n = arr.length;

        if(getProduct (arr, n, x))
            System.out.println("Yes, it has Product Pair");
        else
            System.out.println("No, it does not have Product Pair");
    }
}
Yes, it has Product Pair

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

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഹാഷ്‌സെറ്റ് ഉപയോഗിച്ചതിനാൽ, O (1) സമയത്ത് ഉൾപ്പെടുത്തൽ, ഇല്ലാതാക്കൽ, തിരയൽ എന്നിവ നടത്താൻ ഞങ്ങൾക്ക് കഴിഞ്ഞു. ഇക്കാരണത്താൽ ഞങ്ങൾക്ക് രേഖീയ സമയ സങ്കീർണ്ണത കൈവരിക്കാൻ കഴിഞ്ഞു.

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. എല്ലാ ഘടകങ്ങളും ഹാഷ്‌സെറ്റിൽ സംഭരിക്കുകയാണെങ്കിൽ, അതിന് N നിബന്ധനകൾ ഉണ്ടായിരിക്കും. അത് ഞങ്ങൾക്ക് ലീനിയർ ഇടം നൽകും. കാരണം ഇൻപുട്ട് കൂടുന്നതിനനുസരിച്ച് ഇടം വർദ്ധിക്കുന്നു.