ספרו את מספר השלישיות עם המוצר השווה למספר הנתון


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית סיסקו Flipkart קוליזה פובליסיס סאפיינט
מערך בליל שני מצביעים

הבעיה "ספירת מספר שלישייה עם מוצר שווה למספר נתון" קובעת כי אנו מקבלים מערך שלם ומספר 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. הכריז א מַפָּה.
  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. אנחנו לא נשתמש בגישה נאיבית כדי לפתור את השאלה הזו, זה עולה לנו יותר זמן. במקום לבקר בבחירת כל רכיב בשלישייה, נשתמש חבטות.

נחצה את המערך הנתון ונאחסן את האינדקס של כל אלמנט מערך במפה יחד עם אלמנט המערך הנתון. זה נעשה מכיוון שבהמשך אנו הולכים לבדוק אם אין לחזור על האלמנט שמצאנו. אם לאלמנט יש אותו אינדקס. פירוש הדבר שאיננו סופרים פעמיים את אותו אלמנט המערך לשלישייה.

לאחר חציית המערך, יש לנו את הערכים ב- hashmap. הגדר את ערך הפלט ל- 0. כעת נשתמש בלולאה מקוננת. בו אנו לוקחים אלמנט בלולאה החיצונית ובלולאה הפנימית נבחר אלמנט אחר. ואז אנחנו נגלה את האלמנט השלישי. כל התנאים הטמונים ב'אם הצהרה 'משמשים לגלות את היסוד השלישי. לאחר שעשינו את arr [i] * arr [j] כל מה שאנחנו צריכים למצוא הוא האלמנט השלישי. אז בנימה פשוטה, אם * 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

קוד Java כדי לספור את מספר השלישיות עם המוצר השווה למספר הנתון

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" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו בשתי לולאות מקוננות והשתמשנו ב- Hashmap לחיפוש האלמנט השלישי. לכן, פעולת חיפוש זו נעשית על ידי HashMap ב- O (1) שנעשתה בעבר ב- O (N) בגישה נאיבית. לפיכך האצה זו נובעת מה- HashMap.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שנאחסן את כל האלמנטים במפה. מורכבות החלל היא לינארית.