Сопряжение с данным продуктом


Сложный уровень средний
Часто спрашивают в 24 * 7 инновационных лабораторий Амазонка Avalara Quora Roblox
массив Hash Экзамен Математики

В задаче «Сопряжение с данным продуктом» указано, что вам дается целое массив и число «х». Определите, состоит ли массив из пары, продукт которой равен '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. Если нет, верните false.
  3. В то время как я <п.
    1. Проверить, равен ли один из элементов массива 0
      1. Если x также задано 0, вернуть true.
    2. Проверьте, можно ли разделить x на любой из элементов arr и получить остаток 0.
      1. Если HashSet содержит (x / arr [i]), вернуть true.
      2. Добавьте arr [i] в ​​HashSet.
  4. Вернуть false.

объяснение

Нам дается задача, в которой даны массив и число. Затем мы должны выяснить, существует ли какая-либо пара во входном массиве, у которой Product, равный x. Мы собираемся использовать Хеширования Для решения этой проблемы. Чтобы узнать значение, которое существует в массиве с данным Product. Мы делим x на arr [i] и проверяем, равен ли остаток 0. Если окажется, что он равен 0, мы проверим, существует ли x / arr [i] в ​​HashSet. Если он существует, мы вернем true. Если нет, просто добавьте этот массив элементов в 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.

Это означает, что у нас есть пара Product как 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 терминов. Это будет стоить нам линейного пространства. Потому что по мере увеличения ввода пространство увеличивается.