Número de formas de eliminar elementos para maximizar la media aritmética

Dada una array arr[] , la tarea es encontrar el número de formas de eliminar elementos de la array para maximizar la media aritmética de la array restante.
Ejemplos: 

Entrada: arr[] = { 1, 2, 1, 2 } 
Salida: 3
Eliminar elementos en los índices: 
{ 0, 1, 2 } 
{ 0, 2, 3 } 
{ 0, 2 } 

Entrada: arr[] = { 1, 2, 3 } 
Salida: 1 
 

Enfoque: la media aritmética de la array se maximiza cuando solo quedan los elementos máximos en la array.  
Ahora considere la array arr[] = { 3, 3, 3, 3 } 
Solo debemos asegurarnos de que al menos una instancia del elemento máximo permanezca en la array después de eliminar los otros elementos. Esto garantizará la maximización de la media aritmética. Por lo tanto, debemos eliminar como máximo 3 elementos de la array anterior. El número de formas de eliminar como máximo 3 elementos:

1. Cero elementos eliminados. Número de vías = 1.
2. Un elemento eliminado. Número de vías = 4.
3. Dos elementos eliminados. Número de vías = 6.
4. Tres elementos eliminados. Número de vías = 4.

Por lo tanto total = 1 + 4 + 6 + 4 = 15 = 2 ⁴ – 1.
Ahora considere la array = { 1, 4, 3, 2, 3, 4, 4 } 
Al ordenar la array se convierte en = { 1, 2, 3 , 3, 4, 4, 4 }. En este caso, hay elementos distintos a 4. Podemos quitar como máximo 2 instancias de 4 y cuando esas instancias se eliminen, los otros elementos (que no son 4) siempre deben eliminarse con ellos. Por lo tanto, el número de formas seguirá siendo el mismo que el número de formas de eliminar como máximo 2 instancias de 4.
Las diversas formas de eliminar elementos: 
{ 1, 2, 3, 3 } 
{ 1, 2, 3, 3, 4 } 
{ 1, 2, 3, 3, 4 } 
{ 1, 2, 3, 3, 4 } 
{ 1, 2, 3, 3, 4, 4 } 
{ 1, 2, 3, 3, 4, 4 } 
{ 1 , 2, 3, 3, 4, 4 }
Por lo tanto la respuesta es 2^{recuento de elemento máximo} – 1.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
const int mod = 1000000007;
 
// Function to compute a^n
ll power(ll a, ll n)
{
    if (n == 0)
        return 1;
 
    ll p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if (n & 1)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to return number of ways to maximize arithmetic mean
ll numberOfWays(int* arr, int n)
{
 
    int max_count = 0;
    int max_value = *max_element(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (arr[i] == max_value)
            max_count++;
    }
    return (power(2, max_count) - 1 + mod) % mod;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << numberOfWays(arr, n);
    return 0;
}

// Java implementation of the above approach
import java.util.Arrays;
 
class GFG
{
     
static int mod = 1000000007;
 
// Function to compute a^n
static int power(int a, int n)
{
    if (n == 0)
        return 1;
 
    int p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if ((n & 1) > 0)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to return number of
// ways to maximize arithmetic mean
static int numberOfWays(int []arr, int n)
{
 
    int max_count = 0;
    int max_value = Arrays.stream(arr).max().getAsInt();
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == max_value)
            max_count++;
    }
    return (power(2, max_count) - 1 + mod) % mod;
}
 
// Driver code
public static void main (String[] args)
{
    int []arr = { 1, 2, 1, 2 };
    int n = arr.length;
    System.out.println(numberOfWays(arr, n));
}
}
 
// This code is contributed by mits

# Python3 implementation of the
# above approach
 
mod = 1000000007;
 
# Function to compute a^n
def power(a, n) :
     
    if (n == 0) :
        return 1;
 
    p = power(a, n // 2) % mod;
    p = (p * p) % mod;
    if (n & 1) :
        p = (p * a) % mod;
 
    return p;
 
# Function to return number of ways
# to maximize arithmetic mean
def numberOfWays(arr, n) :
 
    max_count = 0;
    max_value = max(arr)
     
    for i in range(n) :
        if (arr[i] == max_value) :
            max_count += 1;
             
    return (power(2, max_count) - 1 + mod) % mod;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 1, 2 ];
    n = len(arr) ;
     
    print(numberOfWays(arr, n));
 
# This code is contributed by Ryuga

// C# implementation of the above approach
using System;
using System.Linq;
 
class GFG
{
     
static int mod = 1000000007;
 
// Function to compute a^n
static int power(int a, int n)
{
    if (n == 0)
        return 1;
 
    int p = power(a, n / 2) % mod;
    p = (p * p) % mod;
    if ((n & 1)>0)
        p = (p * a) % mod;
 
    return p;
}
 
// Function to return number of
// ways to maximize arithmetic mean
static int numberOfWays(int []arr, int n)
{
 
    int max_count = 0;
    int max_value = arr.Max();
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == max_value)
            max_count++;
    }
    return (power(2, max_count) - 1 + mod) % mod;
}
 
// Driver code
static void Main()
{
    int []arr = { 1, 2, 1, 2 };
    int n = arr.Length;
    Console.WriteLine(numberOfWays(arr, n));
}
}
 
// This code is contributed by mits

<?php
// PHP implementation of the above approach
 
// Function to compute a^n
function power($x, $y, $p)
{
     
    // Initialize result
    $res = 1;
 
    // Update x if it is more
    // than or equal to p
    $x = $x % $p;
 
    while ($y > 0)
    {
        // If y is odd, multiply
        // x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
         
        // y = $y/2
        $y = $y >> 1;
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
// Function to return number of ways
// to maximize arithmetic mean
function numberOfWays($arr, $n)
{
    $mod = 1000000007;
    $max_count = 0;
    $max_value = $arr[0];
    for($i = 0; $i < $n; $i++)
    if($max_value < $arr[$i])
        $max_value = $arr[$i];
     
    for ($i = 0; $i < $n; $i++)
    {
        if ($arr[$i] == $max_value)
            $max_count++;
    }
    return (power(2, $max_count,
                     $mod) - 1 + $mod) % $mod;
}
 
// Driver code
$arr = array( 1, 2, 1, 2 );
$n = 4;
echo numberOfWays($arr, $n);
 
// This code is contributed
// by Arnab Kundu
?>

<script>
    // Javascript implementation of the above approach
     
    let mod = 1000000007;
   
    // Function to compute a^n
    function power(a, n)
    {
        if (n == 0)
            return 1;
 
        let p = power(a, parseInt(n / 2, 10)) % mod;
        p = (p * p) % mod;
        if ((n & 1)>0)
            p = (p * a) % mod;
 
        return p;
    }
 
    // Function to return number of
    // ways to maximize arithmetic mean
    function numberOfWays(arr, n)
    {
 
        let max_count = 0;
        let max_value = Number.MIN_VALUE;
        for (let i = 0; i < n; i++)
        {
            max_value = Math.max(max_value, arr[i]);
        }
        for (let i = 0; i < n; i++)
        {
            if (arr[i] == max_value)
                max_count++;
        }
        return (power(2, max_count) - 1 + mod) % mod;
    }
     
    let arr = [ 1, 2, 1, 2 ];
    let n = arr.length;
    document.write(numberOfWays(arr, n));
 
// This code is contributed by divyeshrabadiya07.
</script>

3

Complejidad de tiempo: O(n + log(max_count))
Espacio auxiliar: O(1)