Проверить, можно ли сократить каждый элемент массива до минимального элемента, заменив его остатком на некоторое число X

Учитывая массив arr[] неотрицательных целых чисел, задача состоит в том, чтобы проверить, могут ли все элементы массива быть уменьшены до минимального элемента в массиве, выбрав любое положительное целое число X и обновив элемент массива arr[i] до arr[i ]%Х . Если это возможно, то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: arr[] = {1, 1, 3, 4}
Output: Yes
Explanation:
Following operations can be performed to reduce all array elements to 1:

1. Choose X = 2 for array element arr[3], and replacing it with arr[3] % 2, modifies the array arr[] to {1, 1, 1, 4}.
2. Choose X = 3 for array element arr[4], and replacing it with arr[4] % 3, modifies the array arr[] to {1, 1, 1, 1}.

After the above operations all array elements have been reduced to the minimum element of arr[]. Therefore, print Yes.

Input: arr[] = {1, 2, 3}
Output: No

Подход: Данную проблему можно решить, используя наблюдение, что любое неотрицательное целое число, скажем, num , можно изменить на следующие целые числа [0, ceil(num/2) – 1] , выбрав значение X как num/2 . Совершенно очевидно, что остальная часть X будет иметь более короткий диапазон измененных чисел, чем X , равный num/2 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, mini , которая хранит минимальный элемент массива arr[] .
• Пройдите по заданному массиву arr[] и, если значение mini не лежит в диапазоне [0, ceil(arr[i]/2) – 1] для любого элемента массива arr[i] , выведите No . В противном случае выведите Да .

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

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