Último elemento restante eliminando los valores más cercanos a la mitad de la suma de Array

Dada una array arr[] de tamaño N , la tarea es encontrar el último elemento restante después de eliminar todos los elementos más cercanos a sum/2 secuencialmente, donde sum es la suma de la array.

Nota: Si sum/2 es decimal, entonces su valor mínimo se considera para la operación y si hay un empate entre los elementos más cercanos, se elimina el más pequeño.

Ejemplos:

Entrada:  N = 4, arr[] = {1, 3, 5, 7}
Salida: 5
Explicación: Iteración 1: {1, 3, 5, 7}, sum = 16, sum/2 = 8, eliminar 7
Iteración 2: {1, 3, 5}, sum = 9, sum/2 = 4, delete 3
Iteración 3: {1, 5}, sum = 6, sum/2 = 3, delete 1
Por fin solo está presente el elemento 5 .

Entrada: N = 4, arr[] = {1, 2, 3, 4}
Salida: 2
Explicación: Iteración 1: {1, 2, 3, 4}, sum = 10, sum/2 = 5, eliminar 4
Iteración 2: {1, 2, 3}, sum = 6, sum/2 = 3, delete 3
Iteración 3: {1, 2}, sum = 3, sum/2 = 1, delete 1
Por fin solo está presente el elemento 2 .

Enfoque : para resolver el problema, siga la siguiente idea:

El problema se relaciona con la búsqueda eficiente de los elementos dentro de la array o el vector y se puede lograr mediante la búsqueda binaria . 
Use un bucle y calcule la suma de la array y elimine el elemento más cercano a sum/2 . Ejecute el ciclo hasta que solo quede un elemento.

Siga los pasos dados para resolver el problema:

• Ordena los N enteros dados.
• Recorre y encuentra la suma de todos los enteros.
• Si bien el tamaño es mayor que 1 , encuentre el índice del elemento más cercano a sum/2
  • Aplique la búsqueda binaria para el propósito y en cada iteración actualice la diferencia para obtener el elemento más cercano.
  • Resta arr[índice] de la suma .
  • Borra el elemento del vector arr en el índice de posición .
• Devuelve el único elemento restante del vector.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the position in the
// vector whose value is closest to the key,
// using binary search
int correctPOS(vector<int>& arr, int n, int key)
{
    int low = 0, high = n - 1, mid;
 
    // Base cases
    if (key <= arr[0])
        return 0;
    else if (key >= arr[n - 1])
        return n - 1;
 
    // Implementation of binary search
    while (low <= high) {
 
        mid = low + (high - low) / 2;
 
        // If the value of arr[mid] is
        // equal to the key, return mid
        if (arr[mid] == key)
            return mid;
 
        // If this is the case
        // then ignore right half
        else if (key < arr[mid]) {
            high = mid - 1;
 
            // Condition to check if the key is
            // in-between arr[mid] and arr[mid-1]
            if (mid > 0 && arr[mid - 1] < key) {
 
                if (abs(key - arr[mid - 1])
                    <= abs(arr[mid] - key))
                    return mid - 1;
                else
                    return mid;
            }
        }
 
        // If this is the case
        // then ignore left half
        else {
            low = mid + 1;
 
            // Condition to check if the key
            // is in-between arr[mid] and arr[mid+1]
            if (mid + 1 < n && arr[mid + 1] > key) {
 
                if (abs(key - arr[mid])
                    <= abs(arr[mid + 1] - key))
                    return mid;
                else
                    return mid + 1;
            }
        }
    }
 
    return mid;
}
 
// Function to find the last
// remaining element
int FindVirus(vector<int>& arr)
{
    int i, index, n = arr.size();
    long long sum = 0;
 
    // Sort the input vector
    sort(arr.begin(), arr.end());
 
    // Traverse the vector to calculate
    // the sum of elements
    for (i = 0; i < n; i++)
        sum += arr[i];
 
    // Run a while loop, while size of vector
    // is greater than one
    while (arr.size() > 1) {
        int index = correctPOS(arr, arr.size(),
                               sum / 2);
        sum -= arr[index];
        arr.erase(arr.begin() + index);
    }
 
    // Return the remaining element
    return arr[0];
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 3, 5, 7 };
 
    // Function call
    cout << FindVirus(arr);
    return 0;
}

// Java program for above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the position in the vector whose
    // value is closest to the key, using binary search
    public static int correctPOS(List<Integer> arr, int n,
                                 int key)
    {
        int low = 0, high = n - 1;
        int mid = 0;
        // Base cases
        if (key <= arr.get(0)) {
            return 0;
        }
        else if (key >= arr.get(n - 1)) {
            return n - 1;
        }
        // Implementation of binary search
        while (low <= high) {
            mid = low + (high - low) / 2;
            // If the value of arr[mid] is equal to the key,
            // return mid
            if (arr.get(mid) == key) {
                return mid;
            }
            // If this is the case then ignore right half
            else if (key < arr.get(mid)) {
                high = mid - 1;
                // Condition to check if the key is
                // in-between arr[mid] and arr[mid-1]
                if (mid > 0 && arr.get(mid - 1) < key) {
                    if (Math.abs(key - arr.get(mid - 1))
                        <= Math.abs(arr.get(mid)) - key) {
                        return mid - 1;
                    }
                    else {
                        return mid;
                    }
                }
            }
            // If this is the case then ignore left half
            else {
                low = mid + 1;
                // Condition to check if the key is
                // in-between arr[mid] and arr[mid+1]
                if (mid + 1 < n && arr.get(mid + 1) > key) {
                    if (Math.abs(key - arr.get(mid))
                        <= Math.abs(arr.get(mid + 1)
                                    - key)) {
                        return mid;
                    }
                    else {
                        return mid + 1;
                    }
                }
            }
        }
        return mid;
    }
 
    // Function to find the last remaining element.
    public static int FindVirus(List<Integer> arr)
    {
        int i, index, n = arr.size();
        int sum = 0;
        // Sort the array
        Collections.sort(arr);
        // Traverse the array to calculate the sum of
        // elements
        for (i = 0; i < n; i++) {
            sum += arr.get(i);
        }
        // Run a while loop, while size of array is greater
        // than one
        while (arr.size() > 1) {
            index = correctPOS(arr, arr.size(), sum / 2);
            sum -= arr.get(index);
            arr.remove(index);
        }
        // Return the remaining element
        return arr.get(0);
    }
 
    public static void main(String[] args)
    {
        List<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        arr.add(3);
        arr.add(5);
        arr.add(7);
 
        // Function call
        System.out.print(FindVirus(arr));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

// C# program for above approach
 
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // Function to find the position in the vector whose
    // value is closest to the key, using binary search
    public static int correctPOS(List<int> arr, int n,
                                 int key)
    {
        int low = 0, high = n - 1;
        int mid = 0;
        // Base cases
        if (key <= arr[0]) {
            return 0;
        }
        else if (key >= arr[n - 1]) {
            return n - 1;
        }
        // Implementation of binary search
        while (low <= high) {
            mid = low + (high - low) / 2;
            // If the value of arr[mid] is equal to the key,
            // return mid
            if (arr[mid] == key) {
                return mid;
            }
            // If this is the case then ignore right half
            else if (key < arr[mid]) {
                high = mid - 1;
                // Condition to check if the key is
                // in-between arr[mid] and arr[mid-1]
                if (mid > 0 && arr[mid - 1] < key) {
                    if (Math.Abs(key - arr[mid - 1])
                        <= Math.Abs(arr[mid]) - key) {
                        return mid - 1;
                    }
                    else {
                        return mid;
                    }
                }
            }
            // If this is the case then ignore left half
            else {
                low = mid + 1;
                // Condition to check if the key is
                // in-between arr[mid] and arr[mid+1]
                if (mid + 1 < n && arr[mid + 1] > key) {
                    if (Math.Abs(key - arr[mid])
                        <= Math.Abs(arr[mid + 1]
                                    - key)) {
                        return mid;
                    }
                    else {
                        return mid + 1;
                    }
                }
            }
        }
        return mid;
    }
 
    // Function to find the last remaining element.
    public static int FindVirus(List<int> arr)
    {
        int i, index, n = arr.Count;
        int sum = 0;
        // Sort the array
        arr.Sort();
        // Traverse the array to calculate the sum of
        // elements
        for (i = 0; i < n; i++) {
            sum += arr[i];
        }
        // Run a while loop, while size of array is greater
        // than one
        while (arr.Count > 1) {
            index = correctPOS(arr, arr.Count, sum / 2);
            sum -= arr[index];
            arr.RemoveAt(index);
        }
        // Return the remaining element
        return arr[0];
    }
 
    public static void Main(String[] args)
    {
        List<int> arr = new List<int>();
        arr.Add(1);
        arr.Add(3);
        arr.Add(5);
        arr.Add(7);
 
        // Function call
        Console.Write(FindVirus(arr));
    }
}
 
 
// This code contributed by shikhasingrajput

8

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)