Maximice la suma de arrays reemplazando pares adyacentes iguales por su suma y X respectivamente

Dados dos números enteros N y X que denotan el tamaño de una array arr[] y el valor inicial de todos los elementos de la array respectivamente, la tarea es encontrar la suma máxima posible de la array dada después de realizar la siguiente operación cualquier número de veces.  

Elija cualquier índice i válido para el cual arr[i] = arr[i + 1] y actualice arr[i] = arr[i] + arr[i + 1] y arr[i + 1] = X .

Ejemplos: 

Entrada: N = 3, X = 5 
Salida: 35 
Explicación: 
Inicialmente arr[] = [5, 5, 5] 
Realizando la operación dada en i = 1, arr[] = [10, 5, 5] 
Realizando la operación dada on i = 2, arr[] = [10, 10, 5] 
Realizando la operación dada on i = 1, arr[] = [20, 5, 5] 
Realizando la operación dada on i = 2, arr[] = [ 20, 10, 5] 
No hay elementos iguales adyacentes en la array. 
Por lo tanto, la suma máxima posible de la array es 35.

Entrada: N = 2, X = 3 
Salida: 9 
Explicación: 
Inicialmente arr[] = [3, 3] 
Realizando la operación dada en i = 1, arr[] = [6, 3] 
No hay elementos iguales adyacentes presentes en el formación. 
Por lo tanto, la suma máxima posible de la array es 9. 

Enfoque ingenuo: la idea es realizar la operación dada en cada índice válido en la array inicial y encontrar la suma máxima posible de todas las reorganizaciones posibles de la array.

Complejidad temporal: O(2 ^N ) 
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la siguiente observación: 

• De los ejemplos antes mencionados, se puede observar que el valor del elemento en el índice i en la array final está dado por: 
   

X * 2 ^(N-i-1)

• Por tanto, la suma del arreglo final será igual a la suma de la serie X * 2 ^{(N – i – 1)} para todo índice válido i .
• La suma de la serie anterior viene dada por: 
   

Suma de la serie = X * (2 ^N – 1) 

Por lo tanto, simplemente imprima X * (2 ^N – 1) como la respuesta requerida. 
 A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to calculate x ^ y
int power(int x, int y)
{
    int temp;
  
    // Base Case
    if (y == 0)
        return 1;
  
    // Find the value in temp
    temp = power(x, y / 2);
  
    // If y is even
    if (y % 2 == 0)
        return temp * temp;
    else
        return x * temp * temp;
}
  
// Function that find the maximum
// possible sum of the array
void maximumPossibleSum(int N, int X)
{
     
    // Print the result using
    // the formula
    cout << (X * (power(2, N) - 1)) << endl;
}
  
// Driver code
int main()
{
    int N = 3, X = 5;
  
    // Function call
    maximumPossibleSum(N, X);
}
 
// This code is contributed by rutvik_56

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to calculate x ^ y
    static int power(int x, int y)
    {
        int temp;
 
        // Base Case
        if (y == 0)
            return 1;
 
        // Find the value in temp
        temp = power(x, y / 2);
 
        // If y is even
        if (y % 2 == 0)
            return temp * temp;
        else
            return x * temp * temp;
    }
 
    // Function that find the maximum
    // possible sum of the array
    public static void
    maximumPossibleSum(int N, int X)
    {
        // Print the result using
        // the formula
        System.out.println(
            X * (power(2, N) - 1));
    }
 
    // Driver Code
    public static void
        main(String[] args)
    {
        int N = 3, X = 5;
 
        // Function Call
        maximumPossibleSum(N, X);
    }
}

# Python3 program for the above approach
 
# Function to calculate x ^ y
def power(x, y):
 
    # Base Case
    if(y == 0):
        return 1
 
    # Find the value in temp
    temp = power(x, y // 2)
 
    # If y is even
    if(y % 2 == 0):
        return temp * temp
    else:
        return x * temp * temp
 
# Function that find the maximum
# possible sum of the array
def maximumPossibleSum(N, X):
 
    # Print the result using
    # the formula
    print(X * (power(2, N) - 1))
 
# Driver Code
N = 3
X = 5
 
# Function call
maximumPossibleSum(N, X)
 
# This code is contributed by Shivam Singh

// C# program for
// the above approach
using System;
class GFG{
 
// Function to calculate x ^ y
static int power(int x, int y)
{
  int temp;
 
  // Base Case
  if (y == 0)
    return 1;
 
  // Find the value in temp
  temp = power(x, y / 2);
 
  // If y is even
  if (y % 2 == 0)
    return temp * temp;
  else
    return x * temp * temp;
}
 
// Function that find the maximum
// possible sum of the array
public static void maximumPossibleSum(int N,
                                      int X)
{
  // Print the result using
  // the formula
  Console.WriteLine(X * (power(2, N) - 1));
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 3, X = 5;
 
  // Function Call
  maximumPossibleSum(N, X);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach   
 
// Function to calculate x ^ y
    function power(x , y) {
        var temp;
 
        // Base Case
        if (y == 0)
            return 1;
 
        // Find the value in temp
        temp = power(x, parseInt(y / 2));
 
        // If y is even
        if (y % 2 == 0)
            return temp * temp;
        else
            return x * temp * temp;
    }
 
    // Function that find the maximum
    // possible sum of the array
    function maximumPossibleSum(N , X)
    {
        // Print the result using
        // the formula
        document.write(X * (power(2, N) - 1));
    }
 
    // Driver Code
     
        var N = 3, X = 5;
 
        // Function Call
        maximumPossibleSum(N, X);
 
// This code contributed by aashish1995
 
</script>

35

Complejidad de tiempo: O(log N) 
Complejidad de espacio: O(1)