கொடுக்கப்பட்ட எண்ணுக்கு சமமான தயாரிப்புடன் மும்மூர்த்திகளின் எண்ணிக்கையை எண்ணுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அகோலைட் அமேசான் சிஸ்கோ , Flipkart குலிசா பப்ளிஸ் சப்பியண்ட்
அணி ஹாஷ் இரண்டு சுட்டிக்காட்டி

“கொடுக்கப்பட்ட எண்ணுக்கு சமமான தயாரிப்புடன் மும்மூர்த்திகளின் எண்ணிக்கையை எண்ணுங்கள்” என்ற சிக்கல் எங்களுக்கு ஒரு முழு வரிசை மற்றும் ஒரு எண் கொடுக்கப்பட்டுள்ளது என்று கூறுகிறது 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

விளக்கம்

மீக்கு சமமான உற்பத்தியை உருவாக்கிய மும்மூர்த்திகள் (2,1,10), (4,5,1)

அல்காரிதம்

  1. ஒரு அறிவிக்கவும் வரைபடம்.
  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] செய்த பிறகு நாம் கண்டுபிடிக்க வேண்டியது மூன்றாவது உறுப்பு மட்டுமே. எனவே ஒரு எளிய குறிப்பில், ஒரு * b * c = m if என்றால் 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” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. நாங்கள் இரண்டு உள்ளமை சுழல்களைப் பயன்படுத்தியுள்ளோம் மற்றும் மூன்றாவது உறுப்பைத் தேட ஹாஷ்மாப்பைப் பயன்படுத்தினோம். எனவே, இந்த தேடல் செயல்பாடு O (1) இல் உள்ள ஹாஷ்மேப்பால் செய்யப்படுகிறது, இது முன்னர் O (N) நேரத்தில் ஒரு அப்பாவி அணுகுமுறையில் செய்யப்பட்டது. இதனால் இந்த வேகத்தை அதிகரிப்பது ஹாஷ்மேப்பின் காரணமாகும்.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஏனென்றால் எல்லா உறுப்புகளையும் வரைபடத்தில் சேமிப்போம். விண்வெளி சிக்கலானது நேரியல்.