ఇచ్చిన సంఖ్యకు సమానమైన ఉత్పత్తితో ముగ్గుల సంఖ్యను లెక్కించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అకోలైట్ అమెజాన్ సిస్కో ఫ్లిప్కార్ట్ కులిజా పబ్లిసిస్ సపియంట్
అర్రే హాష్ రెండు పాయింటర్

“ఇచ్చిన సంఖ్యకు సమానమైన ఉత్పత్తితో ముగ్గురి సంఖ్యను లెక్కించండి” అనే సమస్య మనకు పూర్ణాంక శ్రేణి మరియు సంఖ్యను ఇస్తుందని పేర్కొంది m. M తో సమానమైన ఉత్పత్తితో మొత్తం ముగ్గుల సంఖ్యను కనుగొనమని సమస్య ప్రకటన అడుగుతుంది.

ఉదాహరణ

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

వివరణ

M కి సమానమైన ఉత్పత్తిని సృష్టించిన త్రిపాది (1,5,6), (5,2,3) మరియు (1,3,10)

ఇచ్చిన సంఖ్యకు సమానమైన ఉత్పత్తితో ముగ్గుల సంఖ్యను లెక్కించండి

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

వివరణ

M కి సమానమైన ఉత్పత్తిని సృష్టించిన త్రిపాది (2,1,10), (4,5,1)

అల్గారిథం

  1. ప్రకటించండి a చిహ్నం.
  2. ప్రతి మూలకం యొక్క సూచికను మ్యాప్‌లో భద్రపరచడం ద్వారా నిల్వ చేయండి అమరిక.
  3. అవుట్పుట్ను 0 కి సెట్ చేయండి.
  4. సమూహ లూప్‌ను ఉపయోగించి శ్రేణిని మళ్లీ ప్రయాణిస్తుంది:
    1. ((Arr [i] * arr [j] <= m) && (arr [i] * arr [j]! = 0) && (m% (arr [i] * arr [j]) == 0 )).
      1. ఇది నిజమని తేలితే, m / (arr [i] * arr [j]) ను కనుగొని మ్యాప్‌లో శోధించండి.
    2. మేము కనుగొన్న మూడవ మూలకం ప్రస్తుత రెండు మూలకాలకు సమానం కాదు (arr [i] మరియు arr [j]).
      1. పరిస్థితి సంతృప్తికరంగా ఉంటే, అప్పుడు అవుట్పుట్ సంఖ్యను 1 పెంచండి.
  5. రిటర్న్ అవుట్పుట్.

వివరణ

మా పని ఏమిటంటే, ఇచ్చిన ఉత్పత్తి m కి సమానంగా ఉండే ముగ్గురిని కనుగొనడం. ఈ ప్రశ్నను పరిష్కరించడానికి మేము అమాయక విధానాన్ని ఉపయోగించబోము, దీనికి మాకు ఎక్కువ సమయం ఖర్చవుతుంది. త్రిపాది యొక్క ప్రతి మూలకాన్ని ఎంచుకోవడం కంటే, మేము ఉపయోగిస్తాము హ్యాషింగ్.

మేము ఇచ్చిన శ్రేణిని దాటి, ఇచ్చిన శ్రేణి మూలకంతో పాటు ప్రతి శ్రేణి మూలకం యొక్క సూచికను మ్యాప్‌లో నిల్వ చేస్తాము. ఇది జరుగుతోంది ఎందుకంటే తరువాత, మేము కనుగొన్న మూలకం పునరావృతం కాదా అని తనిఖీ చేయబోతున్నాము. మూలకం ఒకే సూచిక కలిగి ఉంటే. దీని అర్థం మనం ఒకే శ్రేణి మూలకాన్ని త్రిపాది కోసం రెండుసార్లు లెక్కించము.

శ్రేణి యొక్క ట్రావెర్సల్ తరువాత, మనకు హాష్ మ్యాప్‌లో విలువలు ఉన్నాయి. అవుట్పుట్ యొక్క విలువను 0 కి సెట్ చేయండి. ఇప్పుడు, మేము ఒక సమూహ లూప్ను ఉపయోగించబోతున్నాము. దీనిలో మనం బయటి లూప్‌లో ఒక మూలకాన్ని తీసుకుంటాము మరియు లోపలి లూప్‌లో మరొక మూలకాన్ని ఎంచుకుంటాము. అప్పుడు మేము మూడవ మూలకాన్ని కనుగొనబోతున్నాము. మూడవ మూలకాన్ని తెలుసుకోవడానికి 'if statement' లో ఉన్న అన్ని షరతులు ఉపయోగించబడతాయి. Arr [i] * arr [j] చేసిన తరువాత మనం కనుగొనవలసిందల్లా మూడవ మూలకం. కాబట్టి సాధారణ గమనికలో, a * b * c = m if అయితే 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై2 (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. మేము రెండు సమూహ ఉచ్చులను ఉపయోగించాము మరియు మూడవ మూలకం కోసం శోధించడానికి హాష్‌మ్యాప్‌ను ఉపయోగించాము. కాబట్టి, ఈ శోధన ఆపరేషన్ O (1) లోని హాష్ మ్యాప్ చేత చేయబడుతోంది, ఇది గతంలో O (N) సమయంలో అమాయక విధానంలో జరిగింది. ఈ వేగం హాష్ మ్యాప్ కారణంగా ఉంది.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. ఎందుకంటే మేము అన్ని అంశాలను మ్యాప్‌లో నిల్వ చేస్తాము. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.