Проверьте, присутствует ли последний остаток в исходном массиве, уменьшив его на основе заданных условий.

Учитывая массив arr[] натуральных чисел, задача состоит в том, чтобы удалить один элемент спереди и один элемент с конца и найти их произведение, а затем разделить произведение на средний элемент массива и добавить остаток, который мы получили в конец массива и продолжайте ту же операцию, пока размер массива не станет равным 2.

Теперь, когда, наконец, массив содержит только два элемента, произведение обоих элементов делится на размер исходного массива, и мы должны напечатать «YES» , если остаток присутствует в исходном массиве, иначе «NO» .

Пример:

Input: arr[] = {2, 3, 4, 6, 3, 7} 
Output: NO 
Explanation: 
Following are the operations performed on the given array elements:
Pop element from front and rear and divide it by middle and insert remainder into array from rear. 
1. mid = 6, front = 2, rear = 7 remainder will be (2*7) % 6 = 2 modifies the array to arr={3, 4, 6, 3, 2} 
2. mid = 6, front = 3, rear = 2 remainder will be (3*2) % 6 = 0 modifies the array to arr={4, 6, 3, 0} 
3. mid = 3, front = 4, rear = 0 remainder will be (4*0) % 3 = 0 modifies the array to arr={6, 3, 0} 
4. mid = 3, front = 6, rear = 0 remainder will be (6*0) % 3 = 0 modifies the array to arr={3, 0}
After the following operations size of arr=2 so (3*0) % 6 = 0, and 0 is not in arr so return “NO”
Input: arr[] = [2, 3, 4, 8, 5, 7] 
Output: YES 
Reduced array will be [5, 4] 
(5 * 4) % 6 = 2, which is present in Array, so return “YES” 
 

Наивный подход:

• Возьмите mid как средний элемент массива.
• Вставьте элемент спереди и сзади, возьмите его произведение и разделите произведение на средний элемент. (выталкивание элемента из передней части занимает O (N) времени ).
• Вставьте остаток в массив сзади, продолжайте до тех пор, пока размер массива не станет равным 2.
• Теперь разделите произведение элементов на размер исходного массива и проверьте, присутствует ли остаток в исходном массиве или нет.

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

• Скопируйте исходный массив в другой массив и выполните операцию над массивом.
• Возьмите средний элемент в качестве среднего элемента, вытащите элемент спереди и сзади, возьмите его произведение и разделите его на mid .
• Добавьте остаток, который мы получили после деления на массив сзади.
• Повторяйте шаг 2 , пока длина массива не станет равной 2 .
• Наконец, возьмите произведение оставшегося элемента и разделите его на n .
• Если остаток присутствует в исходном массиве, выведите «YES» , иначе выведите «NO» .

Ниже приведена реализация вышеописанного алгоритма.

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

Эффективный подход (с использованием алгоритма двух указателей ) :

• Возьмите начало как 0 и конец как n-1 и найдите средний индекс, взяв сумму начала и конца и разделив ее на 2.
• Найдите остаток после операции и замените последний элемент остатком
• продолжайте выполнять вышеуказанные операции, пока start не станет равным end-1.
• Теперь в массиве останется два элемента, возьмите элементы arr и разделите их произведение на n и проверьте, присутствует ли остаток в исходном массиве или нет.

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

• Скопируйте исходный массив в другой массив и выполните операцию над массивом.
• Начальное начало как 0 и конец как n-1
• Найдите средний индекс как сумму начала и конца, деленную на 2 .
• Найдите остаток, умножив начальный и конечный элементы на средний элемент.
• Замена конечного элемента остатком, увеличение start на 1 , сохраняя end таким же, как n-1 .
• Повторяйте шаг 3 , пока start не станет равным end-1 .
• Взять произведение элементов в начале индекса и в конце массива и разделить на n .
• Если остаток присутствует в исходном массиве, выведите «YES» , иначе «NO» .