התאם למוצר נתון


רמת קושי בינוני
נשאל לעתים קרובות מעבדות חדשנות 24 * 7 אמזון בעברית אבלארה Quora רובלוקס
מערך בליל מתמטיקה

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

דוגמה

[2,30,12,5]
x = 10
Yes, it has Product Pair

הסבר

התאם למוצר נתון

כאן 2 ו- 5 הם האלמנטים שמוצרם שווה ל- 10 כלומר x.

[10,30,12,50]
x = 40
No, it does not have a Product Pair.

הסבר

אין זוג כזה במערך שמוצרו שווה ל- x כלומר 40.

[20,3,12,5]
x = 100
Yes, it has a Product Pair.

הסבר

כאן 20 ו -5 במערך יוצרים זוג שהמוצר שלו שווה ל- x כלומר 100.

אלגוריתם כדי למצוא אם קיים התאמה למוצר נתון

  1. הכריז א HashSet.
  2. בדוק את אורך המערך אם ניתנים לפחות 2 ערכים.
    1. אם לא, החזירו שקר.
  3. בעוד אני <n.
    1. בדוק אם אחד האלמנטים במערך שווה ל- 0
      1. אם ל- x ניתן גם 0, החזר נכון.
    2. בדוק אם ניתן לחלק את x על ידי אלמנטים של arr ונותן את שארית 0.
      1. אם HashSet מכיל (x / arr [i]), חזור נכון.
      2. הוסף את ה- arr [i] ל- HashSet.
  4. החזר שקר.

הסבר

ניתנת לנו בעיה בה ניתן מערך ומספר. ואז עלינו לברר אם קיים זוג כלשהו במערך הקלט שיש לו מוצר השווה ל- x. אנחנו הולכים להשתמש has has לפתור את הבעיה הזאת. כדי לברר את הערך שקיים במערך עם מוצר נתון. אנו מחלקים את ה- x עם arr [i] ונבדוק אם השאר הוא 0. אם נמצא 0 אז נבדוק אם x / arr [i] קיים ב- HashSet. אם זה קיים אז נחזור נכון. אם לא, פשוט הוסף את מערך האלמנטים הזה ל- HashSet לצורך מעבר נוסף.

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

הבה ניקח דוגמא ונבין זאת:

arr [] = {10,20,9,40}, X = 90

i = 0, arr [i] = 10,

נבדוק אם arr [i] שווה ל- 0 אך במערך זה אפילו לא אלמנט אחד הוא 0, כך שהוא לא יבוצע בשום איטרציה.

אנחנו כאן רק נבדוק אם x% arr [i] = = 0 אם זה יעבור אז נבדוק אם x / arr [i] בערכה או לא.

90% 10 == 0 נכון ו- 90/10 = 9 עדיין לא ב- HashSet.

אז נוסיף את arr [i] = 10 לסט.

90% 20 == 0 לא נכון ושום דבר לא קורה

90% 9 == 0 נכון ו- 90/9 = 10 קיים ב- HashSet כפי שכבר הכנסנו ב- HashSet.

אז זה אומר שיש לנו זוג מוצרים כ- 9 ו- 10 במערך ומחזיר true והדפסים

פלט: "כן, יש לו זוג מוצרים".

קוד C ++ למציאת זוג עם מוצר נתון Amazon

#include<iostream>
#include<unordered_set>
using namespace std;
bool getProduct (int arr[], int n, int x)
{
  if (n < 2)
    return false;

  unordered_set<int> s;

  for (int i=0; i<n; i++)
  {
    if (arr[i] == 0)
    {
    if (x == 0)
      return true;
    else
      continue;
    }
    if (x%arr[i] == 0)
    {
      if (s.find(x/arr[i]) != s.end())
                return true;

      s.insert(arr[i]);
    }
  }
  return false;
}
int main()
{
  int arr[] = {10, 20, 9, 40};
  int x = 90;
  int n = sizeof(arr)/sizeof(arr[0]);
  getProduct (arr, n, x)? cout << "Yes, it has Product Pair\n":cout << "No, it does not have Product Pair";
  return 0;
}
Yes, it has Product Pair

קוד Java כדי למצוא התאמה למוצר נתון

import java.util.HashSet;

class pairX
{
    public static boolean getProduct (int arr[], int n, int x)
    {
        HashSet<Integer> mySet = new HashSet<>();

        if(n < 2)
            return false;

        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
            {
                if(x == 0)
                    return true;
                else
                    continue;
            }
            if(x % arr[i] == 0)
            {
                if(mySet.contains(x / arr[i]))
                    return true;

                mySet.add(arr[i]);
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 9, 40};
        int x = 90;
        int n = arr.length;

        if(getProduct (arr, n, x))
            System.out.println("Yes, it has Product Pair");
        else
            System.out.println("No, it does not have Product Pair");
    }
}
Yes, it has Product Pair

ניתוח מורכבות

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך. מכיוון שהשתמשנו ב- HashSet, הצלחנו לבצע הכנסה, מחיקה וחיפוש בזמן O (1). שבגללו הצלחנו להשיג מורכבות זמן ליניארית.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. אם כל האלמנטים יאוחסנו ב- HashSet, אז יהיו לו מונחים N. זה יעלה לנו שטח לינארי. כי ככל שהקלט גדל המרווח גדל.