दिलेल्या उत्पादनासह जोडा  


अडचण पातळी मध्यम
वारंवार विचारले 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. तर मी <एन.
    1. अ‍ॅरेमधील घटकांपैकी एक एक समान आहे की नाही ते तपासा
      1. जर एक्सला 0 देखील दिले तर खरे परत जा.
    2. एर एर च्या कोणत्याही घटकांद्वारे x चे विभाजन केले जाऊ शकते आणि उर्वरित 0 देते का ते तपासा.
      1. जर हॅशसेटमध्ये (x / arr [i]) असेल तर खरे परत जा.
      2. हॅरसेटमध्ये एर [i] जोडा.
  4. खोटे परत.

स्पष्टीकरण

आम्हाला एक समस्या दिली गेली आहे ज्यात अ‍ॅरे आणि नंबर दिला आहे. मग आम्हाला शोधायचे आहे की इनपुट अ‍ॅरेमध्ये कोणतीही जोड जुळली आहे ज्याचे x बरोबर प्रोडक्ट आहे. आम्ही वापरणार आहोत हॅशिंग या समस्येचे निराकरण करण्यासाठी दिलेल्या उत्पादनासह अ‍ॅरेमध्ये असलेले मूल्य शोधण्यासाठी. आम्ही x ला एर बरोबर विभाजित करतो [i] आणि उर्वरित ० आहे का ते तपासा. ० आढळल्यास आम्ही हॅशसेटमध्ये एक्स / एर [i] अस्तित्त्वात असल्याचे तपासू. जर ते अस्तित्त्वात असेल तर आपण खर्‍यास परत जाऊ. नसल्यास, पुढील ट्रॉव्हर्सलसाठी फक्त हॅशसेटमध्ये घटक घटक जोडा.

हे सुद्धा पहा
अ‍ॅरेमध्ये समान घटकांसह निर्देशांक जोड्यांची संख्या

आम्हाला एक अट देखील देण्यात आली आहे जी स्पष्टपणे शून्य उत्पादन तपासण्यासाठी आहे. जर आपले एक्स व्हॅल्यू 0 असे दिले तर आपण अ‍ॅरेचे कोणतेही घटक 0 असल्याचे तपासू. आणि जर ते असेल तर आपण शून्य मिळवू कारण कोणत्याही गोष्टीने शून्य नेहमी शून्य असते.

चला एक उदाहरण घेऊ आणि हे समजू:

अरे [] = {10,20,9,40}, X = 90

i = 0, अरे [i] = 10,

आपण arr [i] 0 च्या बरोबर असल्याचे तपासू परंतु या अ‍ॅरेमध्ये एक घटक देखील 0 नसेल तर तो कोणत्याही पुनरावृत्तीमध्ये कार्यान्वित होणार नाही.

आम्ही येथे हे तपासू की x% एर [i] = = 0 ते उत्तीर्ण झाले की नाही तर आम्ही x / एरर [i] सेट आहे की नाही ते तपासू.

90% 10 == 0 सत्य आहे आणि 90/10 = 9 अद्याप हॅशसेटमध्ये नाही.

म्हणून आपण सेटमध्ये अरर [i] = 10 जोडू.

90% 20 == 0 चुकीचे आहे आणि काहीही घडत नाही

आम्ही आधीच हॅशसेटमध्ये समाविष्ट केल्याप्रमाणे 90% 9 == 0 सत्य आहे आणि 90/9 = 10 हॅशसेटमध्ये उपस्थित आहे.

तर याचा अर्थ असा आहे की आपल्याकडे अ‍ॅरेमध्ये 9 आणि 10 अशी उत्पादन जोड आहे आणि ते खरे आणि मुद्रित होते

आऊटपुट: “होय, यात उत्पाद जोड आहे”.

दिलेल्या प्रॉडक्ट अमाझॉनसह जोडी शोधण्यासाठी सी ++ कोड  

#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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही हॅशसेटचा वापर केल्यामुळे आम्ही ओ (1) वेळेत समाविष्ट करणे, हटविणे आणि शोधण्यात सक्षम होतो. ज्यामुळे आम्ही रेषीय वेळची जटिलता प्राप्त करू शकलो.

हे सुद्धा पहा
सर्व बेरीज 0 बेरीजसह मुद्रित करा

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. जर सर्व घटक हॅशसेटमध्ये संग्रहित केले जातील तर त्यास एन संज्ञा असतील. यासाठी आपल्यास रेषात्मक जागेची किंमत असेल. कारण इनपुट वाढल्यामुळे जागा वाढते.