Спалучэнне з дадзеным прадуктам


Узровень складанасці серада
Часта пытаюцца ў 24 * 7 інавацыйныя лабараторыі амазонка Avalara Quora Roblox
масіў гашыш Матэматыка

Праблема "Спалучэнне з дадзеным прадуктам" абвяшчае, што вам дадзена цэлае масіў і лічба "х". Вызначце, ці складаецца масіў з пары, выраб якой роўны "х" у дадзеным масіве ўводу.

Прыклад

[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.

Тлумачэнне

У масіве няма такой пары, твор якой роўны x, гэта значыць 40.

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

Тлумачэнне

Тут 20 і 5 у масіве ўтвараюць пару, чый твор роўны x, гэта значыць 100.

Алгарытм пошуку наяўнасці пары з дадзеным прадуктам

  1. Абвясціце а HashSet.
  2. Праверце даўжыню масіва, калі зададзена мінімум 2 значэнні.
    1. Калі няма, вярніце false.
  3. У той час як я <n.
    1. Праверце, калі адзін з элементаў масіва роўны 0
      1. Калі х таксама дадзена 0, тады вяртаецца true.
    2. Праверце, ці можна х падзяліць на любы з элементаў arr і дасць астатак 0.
      1. Калі HashSet змяшчае (x / arr [i]), то вяртайце true.
      2. Дадайце arr [i] у HashSet.
  4. Вярнуць ілжыва.

Тлумачэнне

Нам задаецца задача, у якой дадзены масіў і лік. Тады мы павінны высветліць, ці існуе ва ўваходным масіве якая-небудзь пара, якая мае Product, роўную x. Мы збіраемся выкарыстаць мяшанне каб вырашыць гэтую праблему. Каб даведацца значэнне, якое існуе ў масіве з дадзеным Прадуктам. Мы дзелім х з arr [i] і правяраем, ці астатняя частка роўная 0. Калі знойдзена 0, тады мы праверым, ці існуе x / arr [i] у HashSet. Калі ён існуе, мы вернемся праўдай. Калі няма, проста дадайце гэты масіў элемента ў HashSet для далейшага абыходу.

Нам таксама дадзена ўмова, якая заключаецца ў відавочнай праверцы нулявога Тавару. Калі наша значэнне х даецца як 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

Аналіз складанасці

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве. Паколькі мы выкарыстоўвалі HashSet, мы змаглі выканаць ўстаўку, выдаленне і пошук за O (1) раз. З-за чаго нам удалося дасягнуць лінейнай складанасці ў часе.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Калі ўсе элементы будуць захоўвацца ў HashSet, то ў ім будзе N тэрмінаў. Гэта будзе каштаваць нам лінейнай прасторы. Таму што па меры павелічэння ўваходу прастора павялічваецца.