Спарете се со даден производ


Ниво на тешкотија Медиум
Често прашувано во 24 * 7 лаборатории за иновации Амазон Avalara Quora Roblox
Низа Хаш Математика

Проблемот „Пар со даден производ“ наведува дека ви е даден ан број низа и број „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. Е користиме хашинг за да се реши овој проблем. Да се ​​открие вредноста што постои во низата со даден производ. Ние го делиме 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,

Willе провериме дали 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 и ги враќа вистинските и отпечатоците

Излез: „Да, има пар на производи“.

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

Јава код за пронаоѓање Спарување со дадениот производ

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

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

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата. Бидејќи користевме HashSet, можевме да извршиме вметнување, бришење и пребарување во O (1) време. Поради што можевме да постигнеме линеарна временска сложеност.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Ако сите елементи ќе бидат зачувани во HashSet, тогаш тоа ќе има N поими. Тоа ќе не чини линеарен простор. Бидејќи како што се зголемува влезот, просторот се зголемува.