Блог

Как проверить, является ли каждая пара элементов массива такой, что ответ на умножение этой пары существует в массиве.

 Example:
example 1=a={1,2}; here 2*1=2 which exist in array
example 2=a={1,2,1}; here 1*2=2 so 2 exist,2*1=2 so this also exist.
example 3=a={3,4}; here 3*4=12 which doesn't exist in this array
so how we can check that this type of array exist or not.
  

$elements = array(
array(1,2),
array(1,2,1),
array(3,4),
);

foreach ($elements as $subElements) {
foreach ($subElements as $element) {
$product = current($subElements) * next($subElements);
if (in_array($product, $subElements)) {
echo $product.' exists<br>';
}
}
}

1. Храните все элементы в unordered_map(C ) или hashmap (Java)
2. Запустите два for-loop : [first_entry, last_entry) как внешний и (outer_entry, last_entry] как внутренний цикл, выполните суммирование ключа и проверьте, присутствует ли сумма в карте. Если не найден, прервите самый внешний цикл и вернитесь Doesn't exist .
3. Остальное возвращает Exist

Создание карты заняло бы O(N) , а проверка существования парной суммы заняла бы O(N^2)

Итак, TC : O(N^2)

Такой массив должен содержать все элементы, кроме одного, равные 1. В противном случае массив был бы бесконечно большим.