Упарите са датим производом  


Ниво тешкоће Средњи
Често питани у 24 * 7 лабораторија за иновације амазонка Авалара Куора роблок
Ред Хасх Математика

Проблем „Упаривање са датим производом“ наводи да сте добили цео број поредак и број „к“. Утврдите да ли се низ састоји од пара чији производ једнак 'к' постоји у датом улазном низу.

Пример  

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

Објашњење

Упарите са датим производомПин

Овде су 2 и 5 елементи чији је производ једнак 10, тј. Кс.

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

Објашњење

Не постоји такав пар у низу чији је производ једнак к, тј. 40.

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

Објашњење

Овде 20 и 5 у низу чине пар чији је производ једнак к, тј. 100.

Алгоритам за утврђивање да ли постоји упаривање са датим производом  

  1. Изјавите а ХасхСет.
  2. Проверите дужину низа ако су дате најмање 2 вредности.
    1. Ако не, вратите фалсе.
  3. Док и <н.
    1. Проверите да ли је један од елемената низа једнак 0
      1. Ако је к дато и 0, онда вратите труе.
    2. Проверите да ли к може бити подељен са било којим елементом арр и даје остатак 0.
      1. Ако ХасхСет садржи (к / арр [и]), онда вратите труе.
      2. Додајте арр [и] у ХасхСет.
  4. Ретурн фалсе.

Објашњење

Добијамо задатак у коме је дат низ и број. Тада морамо открити постоји ли било који пар у улазном низу који има Продуцт једнак к. Користићемо хасхинг да бисте решили овај проблем. Да бисте сазнали вредност која постоји у низу са датим Производом. Поделимо к са арр [и] и проверимо да ли је остатак 0. Ако се утврди да је 0, проверићемо да ли к / арр [и] постоји у ХасхСет-у. Ако постоји, вратићемо се истином. Ако не, само додајте тај низ елемената у ХасхСет за даље обилажење.

Види такође
Бројање индексних парова са једнаким елементима у низу

Такође смо добили услов који је да изричито проверимо нулти Производ. Ако је наша к вредност дата као 0, проверићемо да ли је било који од елемената низа 0. А ако јесте, онда враћамо труе јер је нула помножена са било чим увек нула.

Узмимо пример и схватимо ово:

арр [] = {10,20,9,40}, Кс = 90

и = 0, арр [и] = 10,

Проверићемо да ли је арр [и] једнако 0, али у овом низу ни један елемент није 0, па се неће извршити ни у једној итерацији.

Овде ћемо само проверити да ли је к% арр [и] = = 0 ако прође онда ћемо проверити да ли је к / арр [и] подешен или није.

90% 10 == 0 је тачно, а 90/10 = 9 још није у ХасхСет-у.

Тако ћемо додати арр [и] = 10 у сет.

90% 20 == 0 је нетачно и ништа се не дешава

90% 9 == 0 је тачно, а 90/9 = 10 је присутно у ХасхСет-у, као што смо већ убацили у ХасхСет.

Дакле, то значи да имамо низ производа као 9 и 10 у низу и враћа труе и исписује

Резултат: „Да, има пар производа“.

Ц ++ код за проналажење пара са датим производом Амазон  

#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

Јава код за проналажење упаривања са датим производом  

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

Анализа сложености  

Сложеност времена

Он) где „Н“ је број елемената у низу. Пошто смо користили ХасхСет, могли смо да извршимо уметање, брисање и претрагу у О (1) времену. Због којих смо успели да постигнемо линеарну временску сложеност.

Види такође
Одштампајте све поднизове са 0 збиром

Сложеност простора

Он) где „Н“ је број елемената у низу. Ако ће сви елементи бити ускладиштени у ХасхСет-у, тада ће имати Н термина. То ће нас коштати линеарног простора. Јер како се улаз повећава простор се повећава.