دی گئی تعداد کے برابر پروڈکٹ والے ٹرپلٹس کی تعداد گنیں  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اکٹھا کرنا ایمیزون سسکو Flipkart کلیزا پبلسس سیپینٹ
لڑی ہیش دو پوائنٹر

مسئلہ "دیئے گئے نمبر کے برابر پروڈکٹ والے ٹرپلٹس کی گنتی کی تعداد" میں یہ بیان کیا گیا ہے کہ ہمیں ایک انٹیجر ارے اور ایک نمبر دیا جاتا ہے۔ m. مسئلے کے بیان میں ایم کے برابر پروڈکٹ کے ٹرپلٹس کی کل تعداد معلوم کرنے کو کہا گیا ہے۔

مثال کے طور پر  

arr[] = {1,5,2,6,10,3}
m=30
3

وضاحت

میٹر کے برابر مصنوع بنانے والے ٹرپلٹس (1,5,6،5,2,3،1,3,10)، (XNUMX،XNUMX،XNUMX) اور (XNUMX،XNUMX،XNUMX) ہیں

دی گئی تعداد کے برابر پروڈکٹ والے ٹرپلٹس کی تعداد گنیںپن

arr[] = {2,4,5,1,10}
m=20
2

وضاحت

میٹر کے برابر مصنوع بنانے والے ٹرپلٹس (2,1,10،4,5,1،XNUMX) ، (XNUMX،XNUMX،XNUMX) ہیں

الگورتھم  

  1. اعلان a نقشہ.
  2. ہر ایک عنصر کی فہرست کو نقشہ میں اسٹور کریں صف.
  3. آؤٹ پٹ کو 0 پر سیٹ کریں۔
  4. نیسڈڈ لوپ کا استعمال کرکے دوبارہ سرے کا سراغ لگانا:
    1. چیک کریں کہ ((آرآر [i] * آر آر [جے] <= م)) اور& (آرآر [i] * ارر [جے]! = 0) اور (ایم آر (آئی آر] [آر آر [جے]) == 0 ))۔
      1. اگر یہ سچ ثابت ہوتا ہے تو ، پھر ایم / (آر آر [i] * ارر [جے]) تلاش کریں اور اسے نقشہ میں تلاش کریں۔
    2. نیز یہ بھی ملاحظہ کریں ، جو تیسرا عنصر ہمیں پایا وہ موجودہ دو عناصر (ارر [i] اور ارر [j]) کے برابر نہیں ہے۔
      1. اگر حالت اطمینان بخش ہو تو آؤٹ پٹ کی گنتی میں 1 اضافہ کریں۔
  5. واپسی کی واپسی

وضاحت

ہمارا کام ان تینوں کو تلاش کرنا ہے جن کی مصنوعہ دیئے گئے نمبر ایم کے برابر ہونی چاہئے۔ ہم اس سوال کو حل کرنے کے لئے کوئی نفیس نقطہ نظر استعمال نہیں کریں گے ، اس میں ہمارے لئے زیادہ وقت خرچ کرنا پڑتا ہے۔ اس کے بجائے ٹرپلٹ کے ہر عنصر کو چننے کے بجائے ، ہم استعمال کریں گے ہیکنگ.

یہ بھی دیکھتے ہیں
پرائم کا الگورتھم

ہم دیئے گئے صفوں کو عبور کریں گے اور دیئے ہوئے سران عنصر کے ساتھ نقشے میں ہر صف عنصر کی اشاریہ کو محفوظ کریں گے۔ یہ اس لئے کیا جا رہا ہے کیونکہ بعد میں ، ہم یہ چیک کرنے جارہے ہیں کہ ہمیں ملنے والے عنصر کو دوبارہ نہیں دہرایا جانا چاہئے۔ اگر عنصر کی ایک ہی فہرست ہے۔ اس کا مطلب یہ ہے کہ ہم تین مرتبہ کے لئے ایک ہی صفی عنصر کو دو بار نہیں گنتے۔

صف کو عبور کرنے کے بعد ، ہیش میپ میں ہمارے پاس اقدار ہیں۔ آؤٹ پٹ کی ویلیو کو 0 پر سیٹ کریں۔ اب ، ہم نیسڈڈ لوپ استعمال کرنے جارہے ہیں۔ جس میں ہم کسی عنصر کو بیرونی لوپ میں لیتے ہیں اور اندرونی لوپ میں اگلا دوسرا عنصر چنتے ہیں۔ پھر ہم تیسرا عنصر تلاش کرنے جا رہے ہیں۔ تیسرا عنصر جاننے کے لئے وہ تمام حالت جو 'if بیان' میں ہے کو استعمال کیا جاتا ہے۔ ارر کرنے کے بعد [i] * ارر [ج] ہمیں جو کچھ تلاش کرنا ہے وہ ہے تیسرا عنصر۔ لہذا ایک عام نوٹ پر ، اگر ایک * b * c = m ⇒ پھر c = m / a * b۔

پھر تیسرا عنصر چیک کریں ، اگر وہ نقشے میں پیش کرتا ہے ، اس کا مطلب ہے کہ ہمیں یہ مل گیا ہے۔ ہمیں صرف یہ دیکھنا ہے کہ کیا عنصر جو ہمیں ملا ہے وہ سہ رخی کے موجودہ دو عناصر کے برابر نہیں ہونا چاہئے۔ نیز ، موجودہ انڈیکس کو اس سے پہلے بھی دہرایا نہیں جانا چاہئے تھا۔ اگر تمام شرائط مطمئن ہیں تو ہم صرف آؤٹ پٹ کی گنتی کو 1 سے بڑھا دیتے ہیں۔ اس کا مطلب ہے کہ ہمارے پاس ایک یا زیادہ ٹرپلٹس ہیں۔ پھر آخر میں صرف آؤٹ پٹ کو واپس کریں۔

C ++ کوڈ جس میں دئے گئے نمبر کے برابر پروڈکٹ والے ٹرپلٹس کی تعداد گننے کے لئے  

#include<iostream>
#include<unordered_map>
using namespace std;

int getProductTriplets(int arr[], int n, int m)
{
    unordered_map<int, int> numindex;
    for (int i = 0; i < n; i++)
        numindex[arr[i]] = i;

    int output = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
            {
                int third = m / (arr[i] * arr[j]);
                auto it = numindex.find(third);

                if (third != arr[i] && third != arr[j]&& it != numindex.end() && it->second > i&& it->second > j)
                    output++;
            }
        }
    }
    return output;
}
int main()
{
    int arr[] = {1,5,2,6,10,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 30;

    cout <<"Total product triplets are: "<<getProductTriplets(arr, n, m);
    return 0;
}
Total product triplets are: 3

جاوا کوڈ جس میں دیئے گئے نمبر کے برابر پروڈکٹ کے ساتھ ٹرپلٹس کی تعداد گننے کے لئے  

import java.util.HashMap;

class TripletProductPair
{
    public static int getProductTriplets(int arr[], int n, int m)
    {
        HashMap<Integer, Integer> numindex = new HashMap<Integer, Integer>(n);
        for (int i = 0; i < n; i++)
            numindex.put(arr[i], i);

        int output = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {

                if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
                {
                    int third = m / (arr[i] * arr[j]);

                    numindex.containsKey(third);
                    if (third != arr[i] && third != arr[j]&& numindex.containsKey(third) && numindex.get(third) > i && numindex.get(third) > j)
                    {
                        output++;
                    }
                }
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,5,2,6,10,3};
        int m = 30;
        System.out.println("Total product triplets are: "+getProductTriplets(arr, arr.length, m));
    }
}
Total product triplets are: 3

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

O (n)2کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے دو گھونسلے والے لوپ استعمال کیے ہیں اور تیسرے عنصر کی تلاش کے ل Hash ہاشمیپ کا استعمال کیا ہے۔ لہذا ، یہ سرچ آپریشن ہاشمیپ کے ذریعہ O (1) میں کیا جارہا ہے جو پہلے او (N) وقت میں ایک نفیس نقطہ نظر میں کیا جارہا تھا۔ اس طرح یہ رفتار ہش میپ کی وجہ سے ہے۔

یہ بھی دیکھتے ہیں
ہر ملازم کے تحت ملازمین کی تعداد تلاش کریں

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ کیونکہ ہم نقشہ میں تمام عناصر کو محفوظ کریں گے۔ خلائی پیچیدگی لکیری ہے۔