Остается последний элемент, удалив два самых больших элемента и заменив их абсолютной разницей, если они не равны
Для массива arr [] из N элементов задача состоит в том, чтобы выполнить следующую операцию:
- Выберите два самых больших элемента из массива и удалите эти элементы. Если элементы не равны, вставьте абсолютную разницу элементов в массив.
- Выполните указанные выше операции, пока в массиве не будет 1 элемента или нет в нем ни одного элемента. Если в массиве остался только один элемент, то распечатайте этот элемент, иначе выведите «-1».
Примеры:
Input: arr[] = { 3, 5, 2, 7 }
Output: 1
Explanation:
The two largest elements are 7 and 5. Discard them. Since both are not equal, insert 7 – 5 = 2 into the array. Hence, arr[] = { 3, 2, 2 }
The two largest elements are 3 and 2. Discard them. Since both are not equal, insert 3 – 2 = 1 into the array. Hence, arr[] = { 1, 2 }
The two largest elements are 2 and 1. Discard them. Since both are not equal, insert 2 – 1 = 1 into the array. Hence, arr[] = { 1 }
The only element left is 1. Print the value of the only element left.Input: arr[] = { 3, 3 }
Output: -1
Explanation:
The two largest elements are 3 and 3. Discard them. Now the array has no elements. So, print -1.
Подход: для решения указанной выше проблемы мы будем использовать структуру данных очереди приоритетов. Ниже приведены шаги:
- Вставьте все элементы массива в очередь приоритета.
- Поскольку приоритетная очередь основана на реализации Max-Heap. Следовательно, удаление элемента из него дает максимальный элемент.
- Пока размер очереди с приоритетом не станет меньше 2, удалите из нее два элемента (скажем, X и Y ) и выполните следующие действия:
- Если X и Y не совпадают, вставьте абсолютное значение X и Y в очередь приоритетов.
- В противном случае вернитесь к шагу 3.
- Если в куче только один элемент, распечатайте этот элемент.
- В противном случае выведите «-1».
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the remaining element int final_element( int arr[], int n) { // Priority queue can be used // to construct max-heap priority_queue< int > heap; // Insert all element of arr[] // into priority queue for ( int i = 0; i < n; i++) heap.push(arr[i]); // Perform operation until heap // size becomes 0 or 1 while (heap.size() > 1) { // Remove largest element int X = heap.top(); heap.pop(); // Remove 2nd largest element int Y = heap.top(); heap.pop(); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = abs (X - Y); heap.push(diff); } } // If heap size is 1, then // print the remaining element if (heap.size() == 1) { cout << heap.top(); } // Else print "-1" else { cout << "-1" ; } } // Driver Code int main() { // Given array arr[] int arr[] = { 3, 5, 2, 7 }; // Size of array arr[] int n = sizeof (arr) / sizeof (arr[0]); // Function Call final_element(arr, n); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.Collections; import java.util.*; class GFG{ // Function to print the remaining element static public int final_element(Integer[] arr, int n) { if (arr == null ) { return 0 ; } // Priority queue can be used // to construct max-heap PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder()); // Insert all element of arr[] // into priority queue for ( int i = 0 ; i < n; i++) { heap.offer(arr[i]); } // Perform operation until heap // size becomes 0 or 1 while (heap.size() > 1 ) { // Remove largest element int X = heap.poll(); // Remove 2nd largest element int Y = heap.poll(); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = Math.abs(X - Y); heap.offer(diff); } } // If heap size is 1, then // print the remaining element // Else print "-1" return heap.size() == 1 ? heap.poll() : - 1 ; } // Driver code public static void main (String[] args) { // Given array arr[] Integer arr[] = new Integer[] { 3 , 5 , 2 , 7 }; // Size of array arr[] int n = arr.length; // Function Call System.out.println(final_element(arr, n)); } } // This code is contributed by deepika_sharma |
Python3
# Python3 program for the above approach from queue import PriorityQueue # Function to print the remaining element def final_element(arr, n): # Priority queue can be used # to construct max-heap heap = PriorityQueue() # Insert all element of # arr[] into priority queue. # Default priority queue in Python # is min-heap so use -1*arr[i] for i in range (n): heap.put( - 1 * arr[i]) # Perform operation until heap # size becomes 0 or 1 while (heap.qsize() > 1 ): # Remove largest element X = - 1 * heap.get() # Remove 2nd largest element Y = - 1 * heap.get() # If extracted elements # are not equal if (X ! = Y): # Find X - Y and push # it to heap diff = abs (X - Y) heap.put( - 1 * diff) # If heap size is 1, then # print the remaining element if (heap.qsize() = = 1 ): print ( - 1 * heap.get()) # Else print "-1" else : print ( "-1" ) # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 3 , 5 , 2 , 7 ] # Size of array arr[] n = len (arr) # Function call final_element(arr, n) # This code is contributed by himanshu77 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the remaining element static void final_element( int [] arr, int n) { // Priority queue can be used // to construct max-heap List< int > heap = new List< int >(); // Insert all element of arr[] // into priority queue for ( int i = 0; i < n; i++) heap.Add(arr[i]); // Perform operation until heap // size becomes 0 or 1 while (heap.Count > 1) { // Remove largest element heap.Sort(); heap.Reverse(); int X = heap[0]; heap.RemoveAt(0); // Remove 2nd largest element int Y = heap[0]; heap.RemoveAt(0); // If extracted element // are not equal if (X != Y) { // Find X - Y and push // it to heap int diff = Math.Abs(X - Y); heap.Add(diff); } } // If heap size is 1, then // print the remaining element if (heap.Count == 1) { heap.Sort(); heap.Reverse(); Console.Write(heap[0]); } // Else print "-1" else { Console.Write(-1); } } // Driver code static void Main() { // Given array arr[] int [] arr = { 3, 5, 2, 7 }; // Size of array arr[] int n = arr.Length; // Function Call final_element(arr, n); } } // This code is contributed by divyeshrabadiya07 |
1
Сложность времени: O (N * log (N))
Вспомогательная космическая сложность: O (N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.