Recuento de formas de convertir una array dada de modo que el máximo de la array no esté presente en la primera mitad

Dada una array arr[] de tamaño par N . La tarea es contar el número de formas de convertir arr[] de modo que la primera mitad del arreglo no contenga el número máximo. 

Ejemplos:

Entrada: arr[] = {2, 2, 5, 2, 2, 2}
Salida: 3
Explicación: Las siguientes son las formas en las que el elemento máximo 5 no está presente en la primera mitad de la array.
[2, 2, 2, 5, 2, 2] cuando x=1 (desplazado a la derecha en 1)
[2, 2, 2, 2, 5, 2] cuando x=2 (desplazado a la derecha en 2)
[2, 2, 2, 2, 2, 5] cuando x=3 (desplazado a la derecha por 3)
[5, 2, 2, 2, 2, 2] cuando x=4 NO ES UN CASO VÁLIDO

Entrada: arr[] = {3, 3, 6, 3, 3, 6}
Salida: 0
Explicación: No importa cuántos turnos realicemos, el número máximo 6 siempre está presente en la primera array.

Enfoque ingenuo: haga cambios a la derecha en arr[] y verifique cada caso de acuerdo con la condición dada. Cuenta todas las formas posibles e imprímelo.

Complejidad temporal: O(N * N)
Espacio auxiliar: O(1)

Enfoque eficiente: este problema se basa en la implementación. Siga los pasos a continuación para resolver el problema dado.

• Tome dos mitades de la array arr[] .
• Encuentre y guarde el valor máximo en el vector.
• Tome una variable para almacenar el valor máximo de arr[] .
• Dado que el valor máximo puede ocurrir más de una vez en la array, guarde la posición del valor máximo al frente y al final.
• Si la posición del valor máximo es tal que es menos de la mitad del tamaño de la array, no será posible que la mitad frontal de la array no tenga un valor tan grande.
• Y si ese no es el caso, entonces el número de formas posibles sería N/2 – (última posición – primera posición).

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 number of ways to
// achieve the required array
void countWays(vector<int>& arr)
{
    int last_pos = -1;
    int front_pos = -1;
    int N = arr.size();
    int maxi = INT_MIN;
    for (int i = 0; i < N; i++) {
        maxi = max(maxi, arr[i]);
    }
    for (int i = 0; i < N; i++) {
        if (arr[i] == maxi) {
            front_pos = i;
            break;
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        if (arr[i] == maxi) {
            last_pos = i;
            break;
        }
    }
 
    if (N / 2 >= (last_pos - front_pos))
        cout << (N / 2 - (last_pos - front_pos));
    else
        cout << "0";
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 2, 5, 2, 2, 2 };
 
    // Function Call
    countWays(arr);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find the number of ways to
  // achieve the required array
  static void countWays(int arr[])
  {
    int last_pos = -1;
    int front_pos = -1;
    int N = arr.length;
    int maxi = Integer.MIN_VALUE;
    for (int i = 0; i < N; i++) {
      maxi = Math.max(maxi, arr[i]);
    }
    for (int i = 0; i < N; i++) {
      if (arr[i] == maxi) {
        front_pos = i;
        break;
      }
    }
    for (int i = N - 1; i >= 0; i--) {
      if (arr[i] == maxi) {
        last_pos = i;
        break;
      }
    }
 
    if (N / 2 >= (last_pos - front_pos))
      System.out.println(N / 2 - (last_pos - front_pos));
    else
      System.out.println("0");
  }
 
  // Driver Code
  public static void main (String[] args) {
    int arr[] = { 2, 2, 5, 2, 2, 2 };
 
    // Function Call
    countWays(arr);
  }
}
 
// This code is contributed by hrithikgarg03188.

# python3 program for above approach
INT_MIN = -2147483648
 
# Function to find the number of ways to
# achieve the required array
def countWays(arr):
 
    last_pos = -1
    front_pos = -1
    N = len(arr)
    maxi = INT_MIN
    for i in range(0, N):
        maxi = max(maxi, arr[i])
 
    for i in range(0, N):
        if (arr[i] == maxi):
            front_pos = i
            break
 
    for i in range(N - 1, -1, -1):
        if (arr[i] == maxi):
            last_pos = i
            break
 
    if (N // 2 >= (last_pos - front_pos)):
        print(N // 2 - (last_pos - front_pos))
    else:
        print("0")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [2, 2, 5, 2, 2, 2]
 
    # Function Call
    countWays(arr)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
 
  // Function to find the number of ways to
  // achieve the required array
  static void countWays(int []arr)
  {
    int last_pos = -1;
    int front_pos = -1;
    int N = arr.Length;
    int maxi = int.MinValue;
    for (int i = 0; i < N; i++) {
      maxi = Math.Max(maxi, arr[i]);
    }
    for (int i = 0; i < N; i++) {
      if (arr[i] == maxi) {
        front_pos = i;
        break;
      }
    }
    for (int i = N - 1; i >= 0; i--) {
      if (arr[i] == maxi) {
        last_pos = i;
        break;
      }
    }
 
    if (N / 2 >= (last_pos - front_pos))
      Console.WriteLine(N / 2 - (last_pos - front_pos));
    else
      Console.WriteLine("0");
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []arr = { 2, 2, 5, 2, 2, 2 };
 
    // Function Call
    countWays(arr);
  }
}
 
// This code is contributed by shikhasingrajput

<script>
      // JavaScript code for the above approach
 
      // Function to find the number of ways to
      // achieve the required array
      function countWays(arr)
      {
          let last_pos = -1;
          let front_pos = -1;
          let N = arr.length;
          let maxi = Number.MIN_VALUE;
          for (let i = 0; i < N; i++) {
              maxi = Math.max(maxi, arr[i]);
          }
          for (let i = 0; i < N; i++) {
              if (arr[i] == maxi) {
                  front_pos = i;
                  break;
              }
          }
          for (let i = N - 1; i >= 0; i--) {
              if (arr[i] == maxi) {
                  last_pos = i;
                  break;
              }
          }
 
          if (Math.floor(N / 2) >= (last_pos - front_pos))
              document.write(Math.floor(N / 2) - (last_pos - front_pos));
          else
              document.write("0");
      }
 
      // Driver Code
      let arr = [2, 2, 5, 2, 2, 2];
 
      // Function Call
      countWays(arr);
 
     // This code is contributed by Potta Lokesh
  </script>

3

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