Проверить наличие целого числа между min и max массива, которое делит все элементы массива

Опубликовано: 26 Февраля, 2023

Учитывая массив A[] размера N , задача состоит в том, чтобы проверить, существует ли какое-либо целое число, которое делит все элементы этого массива и лежит в диапазоне минимального и максимального элементов (включая оба) этого массива.

Примеры:

Input: A = {27, 6, 9, 3, 21}
Output: 1
Explanation: Here, 3 lies between min(3) and max(27) of this array,  
and divides all elements of this array.

Input: A = {4, 7, 12, 13, 20}
Output: 0
Explanation: No number between 4 and 20 (both included) divides 
all the elements in the array.

Подход:

 The idea is to simply check for all possible numbers between minimum and maximum element of the array, whether any of them divides all the elements of that array or not.

Выполните следующие шаги, чтобы реализовать эту идею:

  • Используйте два вложенных цикла: один от минимального элемента к максимальному элементу и один для проверки, делит ли он все числа или нет.
  • Во вложенном цикле инициализируйте count равным 0 и увеличивайте счетчик всякий раз, когда он делит значение.
  • Если на какой-либо итерации счетчик становится равным N, то вернуть true.
  • В противном случае, если такой элемент не найден, вернуть false.

Ниже приведена реализация этого подхода:

Time Complexity: O(d * N), where d = max_element – min_element

Space Complexity: O(1)

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