Manipulación de array y suma

Dada una array arr[] de N enteros y un entero S . La tarea es encontrar un elemento K en la array tal que si todos los elementos de la array > K se hacen iguales a K entonces la suma de todos los elementos de la array resultante se vuelve igual a S . Si no es posible encontrar dicho elemento, imprima -1 .
Ejemplos: 
 

Entrada: M = 15, arr[] = {12, 3, 6, 7, 8} 
Salida: 3 
Array resultante = {3, 3, 3, 3, 3} 
Suma de los elementos de la array = 15 = S
Entrada: M = 5, array[] = {1, 3, 2, 5, 8} 
Salida: 1 
 

Enfoque: Ordenar la array. Recorra la array considerando que el valor de K es igual al elemento actual y luego verifique si la suma de los elementos anteriores + (K * número de elementos restantes) = S . En caso afirmativo , imprima el valor de K , si no se encuentra dicho elemento, imprima -1 al final.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the required element
int getElement(int a[], int n, int S)
{
    // Sort the array
    sort(a, a + n);
 
    int sum = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current element
        // satisfies the condition
        if (sum + (a[i] * (n - i)) == S)
            return a[i];
        sum += a[i];
    }
 
    // No element found
    return -1;
}
 
// Driver code
int main()
{
    int S = 5;
    int a[] = { 1, 3, 2, 5, 8 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << getElement(a, n, S);
 
    return 0;
}

//Java implementation of the approach
import java.util.Arrays;
 
class GFG
{
    // Function to return the required element
    static int getElement(int a[], int n, int S)
    {
        // Sort the array
        Arrays.sort(a);
     
        int sum = 0;
     
        for (int i = 0; i < n; i++)
        {
     
            // If current element
            // satisfies the condition
            if (sum + (a[i] * (n - i)) == S)
                return a[i];
            sum += a[i];
        }
     
        // No element found
        return -1;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        int S = 5;
        int a[] = { 1, 3, 2, 5, 8 };
        int n = a.length;
     
        System.out.println(getElement(a, n, S));
    }
}
 
// This code is contributed by Mukul singh.

# Python3 implementation of the approach
 
# Function to return the required element
def getElement(a, n, S) :
     
    # Sort the array
    a.sort();
 
    sum = 0;
 
    for i in range(n) :
         
        # If current element
        # satisfies the condition
        if (sum + (a[i] * (n - i)) == S) :
            return a[i];
             
        sum += a[i];
 
    # No element found
    return -1;
 
# Driver Code
if __name__ == "__main__" :
     
    S = 5;
    a = [ 1, 3, 2, 5, 8 ];
    n = len(a) ;
 
    print(getElement(a, n, S)) ;
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to return the required element
    static int getElement(int[] a, int n, int S)
    {
        // Sort the array
        Array.Sort(a);
     
        int sum = 0;
     
        for (int i = 0; i < n; i++)
        {
     
            // If current element
            // satisfies the condition
            if (sum + (a[i] * (n - i)) == S)
                return a[i];
            sum += a[i];
        }
     
        // No element found
        return -1;
    }
     
    // Driver code
    public static void Main()
    {
        int S = 5;
        int[] a = { 1, 3, 2, 5, 8 };
        int n = a.Length;
     
        Console.WriteLine(getElement(a, n, S));
    }
}
 
// This code is contributed by Mukul singh.

<?php
// PHP implementation of the approach
 
// Function to return the required element
function getElement($a, $n, $S)
{
    // Sort the array
    sort($a, 0);
 
    $sum = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
 
        // If current element
        // satisfies the condition
        if ($sum + ($a[$i] *
           ($n - $i)) == $S)
            return $a[$i];
        $sum += $a[$i];
    }
 
    // No element found
    return -1;
}
 
// Driver code
$S = 5;
$a = array(1, 3, 2, 5, 8);
$n = sizeof($a);
 
echo getElement($a, $n, $S);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 //Javascript implementation of the approach
 
// Function to return the required element
function getElement(a, n, S)
{
    // Sort the array
    a.sort();
 
    var sum = 0;
 
    for (var i = 0; i < n; i++) {
 
        // If current element
        // satisfies the condition
        if (sum + (a[i] * (n - i)) == S)
            return a[i];
        sum += a[i];
    }
 
    // No element found
    return -1;
}
 
var S = 5;
var a = [ 1, 3, 2, 5, 8 ];
var n = a.length;
document.write(getElement(a, n, S));
 
 
// This code is contributed by SoumikMondal
</script>

1

Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)