Найдите недостающее значение из массива B, образованного путем добавления некоторого значения X к массиву A.

Опубликовано: 21 Сентября, 2022

Даны два массива arr1[] и arr2[] размера N и N – 1 соответственно. Каждое значение в arr2[] получается путем добавления скрытого значения, скажем, X к любому arr1[i] N-1 раз, что означает, что для любого i arr1[i]+X не включен в arr2[] , то есть отсутствующий значение в arr2[] . Задача состоит в том, чтобы найти как скрытое значение X , так и отсутствующее значение, которое не выбрано из arr1[] .

Примеры:

Input: arr1[] = {3, 6, 5, 10}, arr2[] = {17, 10, 13}
Output: Hidden = 7, Missing = 5
Explanation: The elements of the second array are obtained in the following way:
First element: (10 + 7) = 17, 10 is the element at index 4 of arr1[]
Second element: (3 + 7) = 10, 3 is the element at index 0 of arr1[]
Third element: (6 + 7) = 13, 6 is the element at index 1 of arr1[]
So, 7 is the hidden value and 5 is the missing value.

Input: arr1[] = {4, 1, 7}, arr2[] = {4, 10}
Output: Hidden = 3, Missing = 4

Подход: Эта проблема может быть решена с помощью

  • Отсортируйте оба заданных массива в порядке неубывания.
  • Создайте неупорядоченную карту для хранения различий.
  • Пройдите массивы до N – 1 и проверьте значения, сохранив различия элементов обоих массивов.
    • Пусть a = arr2[i] – arr1[i] и b = arr2[i] – arr1[i+1] .
    • Если a!=b , то проверьте,
      • a > 0 , затем сохраните его в карте.
      • b > 0 , затем сохраните его в карте.
    • иначе проверьте, если a> 0, затем сохраните его на карте.
  • Переберите карту, найдите скрытое значение и распечатайте его.
  • Перейдите arr1[] , добавив скрытое значение, и проверьте, присутствует ли оно в arr2[] , иначе напечатайте отсутствующее значение.

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N)

Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ