दी गई संख्या के बराबर उत्पाद के साथ ट्रिपल की संख्या की गणना करें


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट वीरांगना सिस्को फ्लिपकार्ट कुलिजा पब्लिसिस सैपिएंट
ऐरे हैश दो सूचक

समस्या "दी गई संख्या के बराबर उत्पाद के साथ ट्रिपल की संख्या की गणना" बताती है कि हमें एक पूर्णांक सरणी और एक संख्या दी गई है m। समस्या कथन उत्पाद के साथ ट्रिपलेट्स की कुल संख्या का पता लगाने के लिए कहता है।

उदाहरण

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

व्याख्या

ट्रिपल जो एम के बराबर उत्पाद बनाते हैं (1,5,6), (5,2,3) और (1,3,10)

दी गई संख्या के बराबर उत्पाद के साथ ट्रिपल की संख्या की गणना करें

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

व्याख्या

ट्रिपल जो एम के बराबर उत्पाद बनाते हैं (2,1,10), (4,5,1)

कलन विधि

  1. डिक्लेयर ए नक्शा.
  2. प्रत्येक तत्व के सूचकांक को ट्रैवर्सिंग करके मानचित्र में संग्रहीत करें सरणी.
  3. आउटपुट को 0 पर सेट करें।
  4. नेस्टेड लूप का उपयोग करके सरणी को फिर से ट्रैवर्स करना
    1. जांचें कि क्या ((गिरफ्तारी [i] * गिरफ्तारी [j] <= m) && (गिरफ्तार [i] * गिरफ्तार [j]! = 0) और& (m% (गिरफ्तार [i] * गिरफ्तार [j] == ०) ))।
      1. यदि यह सत्य पाया जाता है, तो m / (arr [i] * arrest [j]) का पता लगाएं और इसे मानचित्र में खोजें।
    2. यह भी जांच लें, जो तीसरा तत्व हमने पाया है वह वर्तमान दो तत्वों (गिरफ्तारी [i] और गिरफ्तार [j] के बराबर नहीं है।
      1. यदि स्थिति संतुष्ट होती है, तो आउटपुट की संख्या 1 से बढ़ाएं।
  5. वापसी आउटपुट।

व्याख्या

हमारा काम उन ट्रिपल का पता लगाना है जिनका उत्पाद दिए गए नंबर m के बराबर होना चाहिए। हम इस प्रश्न को हल करने के लिए एक भोले दृष्टिकोण का उपयोग नहीं करने जा रहे हैं, इससे हमें अधिक समय लगता है। ट्रिपलेट के प्रत्येक तत्व को लेने के बजाय, हम उपयोग करेंगे hashing.

हम दिए गए सरणी को पार करेंगे और दिए गए सरणी तत्व के साथ नक्शे में प्रत्येक सरणी तत्व के सूचकांक को संग्रहीत करेंगे। ऐसा इसलिए किया जा रहा है क्योंकि बाद में, हम जाँचने जा रहे हैं कि क्या हमने पाया तत्व दोहराया नहीं जाना चाहिए। यदि तत्व में एक ही सूचकांक है। इसका मतलब यह है कि हम ट्रिपलेट के लिए एक ही सरणी तत्व को दो बार नहीं गिनते हैं।

सरणी के ट्रैवर्सल के बाद, हमारे पास हैशमैप में मान हैं। आउटपुट का मान 0. पर सेट करें। अब, हम नेस्टेड लूप का उपयोग करने जा रहे हैं। जिसमें हम बाहरी लूप में एक तत्व लेते हैं और अगले लूप में एक और तत्व लेते हैं। फिर हम तीसरे तत्व का पता लगाने जा रहे हैं। तीसरी स्थिति का पता लगाने के लिए statement यदि कथन ’में निहित सभी शर्त का उपयोग किया जाता है। गिरफ्तारी करने के बाद [i] * गिरफ्तारी [j] हम सभी को पता लगाना है कि तीसरा तत्व है। तो एक सरल नोट पर, यदि एक * b * c = m ⇒ तो c = m / a * b।

फिर तीसरे तत्व की जांच करें, अगर यह मानचित्र में प्रस्तुत करता है, तो इसका मतलब है कि हमने इसे ढूंढ लिया है। हमें बस यह जांचना है कि क्या हमने पाया तत्व ट्रिपलेट के वर्तमान दो तत्वों के बराबर नहीं होना चाहिए। इसके अलावा, वर्तमान सूचकांक को पहले नहीं दोहराया जाना चाहिए था। यदि सभी स्थितियां संतुष्ट हैं तो हम सिर्फ आउटपुट की संख्या को 1 से बढ़ाते हैं। इसका मतलब है कि हमारे पास एक या अधिक ट्रिपल हैं। फिर अंत में बस आउटपुट वापस करें।

सी ++ कोड दिए गए नंबर के बराबर उत्पाद के साथ ट्रिपल की संख्या की गणना करने के लिए

#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

जटिलता विश्लेषण

समय जटिलता

पर2जहां "N" सरणी में तत्वों की संख्या है। चूंकि हमने दो नेस्टेड लूप्स का इस्तेमाल किया है और तीसरे तत्व की खोज के लिए हैशमैप का इस्तेमाल किया है। तो, यह खोज ऑपरेशन ओ (1) में हाशप द्वारा किया जा रहा है जो पहले ओ (एन) समय में एक भोली दृष्टिकोण में किया जा रहा था। इस प्रकार यह गति हाशप की वजह से है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। क्योंकि हम सभी तत्वों को मानचित्र में संग्रहीत करेंगे। अंतरिक्ष की जटिलता रैखिक है।