തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ ഉൽപ്പന്നമുള്ള ട്രിപ്പിളുകളുടെ എണ്ണം എണ്ണുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ സിസ്കോ ഫ്ലിപ്പ്കാർട്ട് കുലിസ പബ്ലിസിസ് സാപിയന്റ്
അറേ ഹാഷ് രണ്ട് പോയിന്റർ

“തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ ഉൽ‌പ്പന്നമുള്ള ത്രിമൂർത്തികളുടെ എണ്ണം” എന്ന പ്രശ്നം, ഞങ്ങൾക്ക് ഒരു പൂർണ്ണ സംഖ്യയും ഒരു സംഖ്യയും നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു m. 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

വിശദീകരണം

M ന് തുല്യമായ ഉൽ‌പന്നമായി രൂപപ്പെടുന്ന ത്രിമൂർത്തികൾ (2,1,10), (4,5,1)

അൽഗോരിതം  

  1. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  2. കടന്നുപോകുന്നതിലൂടെ ഓരോ ഘടകത്തിന്റെയും സൂചിക മാപ്പിൽ സംഭരിക്കുക ശ്രേണി.
  3. Output ട്ട്‌പുട്ട് 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. അവസ്ഥ തൃപ്‌തികരമാണെങ്കിൽ, output ട്ട്‌പുട്ടിന്റെ എണ്ണം 1 വർദ്ധിപ്പിക്കുക.
  5. Return ട്ട്‌പുട്ട് നൽകുന്നു.

വിശദീകരണം

തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായിരിക്കേണ്ട ത്രിമൂർത്തികളെ കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഈ ചോദ്യം പരിഹരിക്കുന്നതിന് ഞങ്ങൾ നിഷ്കളങ്കമായ ഒരു സമീപനം ഉപയോഗിക്കാൻ പോകുന്നില്ല, ഇതിന് ഞങ്ങൾക്ക് കൂടുതൽ സമയം ചിലവാകും. ട്രിപ്പിളിന്റെ ഓരോ ഘടകങ്ങളും തിരഞ്ഞെടുക്കുന്നത് സന്ദർശിക്കുന്നതിനുപകരം, ഞങ്ങൾ ഉപയോഗിക്കും ഹാഷിംഗ്.

ഇതും കാണുക
പ്രിമിന്റെ അൽഗോരിതം

തന്നിരിക്കുന്ന അറേ ഘടകത്തിലൂടെ ഞങ്ങൾ ഓരോ അറേ ഘടകത്തിന്റെയും സൂചിക മാപ്പിലേക്ക് സംഭരിക്കും. ഇത് ചെയ്യുന്നത് കാരണം പിന്നീട്, ഞങ്ങൾ കണ്ടെത്തിയ ഘടകം ആവർത്തിക്കേണ്ടതില്ലേ എന്ന് പരിശോധിക്കാൻ പോകുന്നു. ഘടകത്തിന് സമാന സൂചിക ഉണ്ടെങ്കിൽ. ഇതിനർത്ഥം ഞങ്ങൾ ഒരേ അറേ ഘടകത്തെ ട്രിപ്പിളിനായി രണ്ടുതവണ കണക്കാക്കില്ല എന്നാണ്.

അറേയുടെ സഞ്ചാരത്തിനുശേഷം, ഞങ്ങൾക്ക് ഹാഷ്‌മാപ്പിൽ മൂല്യങ്ങളുണ്ട്. Output ട്ട്‌പുട്ടിന്റെ മൂല്യം 0 ആയി സജ്ജമാക്കുക. ഇപ്പോൾ ഞങ്ങൾ ഒരു നെസ്റ്റഡ് ലൂപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു. അതിൽ ഞങ്ങൾ ഒരു മൂലകം പുറത്തെ ലൂപ്പിലും അടുത്ത ലൂപ്പിൽ അടുത്ത ഘടകത്തിലും എടുക്കുന്നു. മൂന്നാമത്തെ ഘടകം കണ്ടെത്താൻ പോകുന്നു. മൂന്നാമത്തെ ഘടകം കണ്ടെത്താൻ 'if statement' എന്നതിലെ എല്ലാ വ്യവസ്ഥകളും ഉപയോഗിക്കുന്നു. Arr [i] * arr [j] ചെയ്തതിന് ശേഷം നമ്മൾ കണ്ടെത്തേണ്ടത് മൂന്നാമത്തെ ഘടകമാണ്. അതിനാൽ ഒരു ലളിതമായ കുറിപ്പിൽ, ഒരു * b * c = m if ആണെങ്കിൽ c = m / a * b.

മൂന്നാമത്തെ ഘടകത്തിനായി പരിശോധിക്കുക, അത് മാപ്പിൽ അവതരിപ്പിക്കുന്നുവെങ്കിൽ, ഞങ്ങൾ അത് കണ്ടെത്തി എന്നാണ് അർത്ഥമാക്കുന്നത്. ഞങ്ങൾ കണ്ടെത്തിയ മൂലകം ട്രിപ്പിളിന്റെ നിലവിലെ രണ്ട് ഘടകങ്ങൾക്ക് തുല്യമാകരുത് എന്ന് പരിശോധിക്കേണ്ടതുണ്ട്. കൂടാതെ, നിലവിലെ സൂചിക മുമ്പ് ആവർത്തിക്കരുത്. എല്ലാ നിബന്ധനകളും തൃപ്തികരമാണെങ്കിൽ output ട്ട്‌പുട്ടിന്റെ എണ്ണം 1 വർദ്ധിപ്പിക്കുകയേ വേണ്ടൂ. ഇതിനർത്ഥം നമുക്ക് ഒന്നോ അതിലധികമോ മൂന്നിരട്ടി ഉണ്ടെന്നാണ്. അവസാനം the ട്ട്‌പുട്ട് തിരികെ നൽകുക.

തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ ഉൽപ്പന്നമുള്ള ട്രിപ്പിളുകളുടെ എണ്ണം കണക്കാക്കാനുള്ള സി ++ കോഡ്  

#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 (n2എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകൾ ഉപയോഗിക്കുകയും മൂന്നാമത്തെ ഘടകത്തിനായി തിരയാൻ ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുകയും ചെയ്തതിനാൽ. അതിനാൽ, ഈ തിരയൽ‌ പ്രവർ‌ത്തനം O (1) ലെ ഹാഷ്‌മാപ്പ് ചെയ്യുന്നു, ഇത് മുമ്പ് O (N) സമയത്ത് നിഷ്‌കളങ്കമായ ഒരു സമീപനത്തിലാണ് നടത്തിയത്. ഹാഷ്മാപ്പ് കാരണം ഈ വേഗത വർദ്ധിക്കുന്നു.

ഇതും കാണുക
എല്ലാ ജീവനക്കാർക്കും കീഴിലുള്ള ജീവനക്കാരുടെ എണ്ണം കണ്ടെത്തുക

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

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾ എല്ലാ ഘടകങ്ങളും മാപ്പിൽ സംഭരിക്കും. സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.