Recuento de reemplazos requeridos para que la suma de todos los pares de tipo dado de la array sea igual

Dada una array de enteros arr de longitud N y un entero K , la tarea es encontrar el número de elementos de la array que se reemplazarán por un valor del rango [1, K] tal que cada par (arr[i], arr[N – 1 – i] tienen igual suma.

Ejemplos:

Entrada: arr[] = {1, 2, 2, 1}, K = 3 
Salida: 1 
Explicación: 
Reemplace arr[0] con 3, de modo que la array se convierta en {3, 2, 2, 1}. 
Ahora, se puede ver que arr[0] + arr[3] = arr[1] + arr[2] = 4.

Entrada: arr[] = {1, 2, 1, 2, 1, 2} 
Salida: 0 
Explicación: 
No es necesario realizar ningún cambio como arr[0] + arr[5] = arr[1] + arr[4] = array[2] + array[3] = 3

Enfoque ingenuo: 
el enfoque más simple para este problema podría ser iterar todos los valores posibles de X , que pueden ser cualquier número en el rango de 1 a 2*K , y encontrar el número de operaciones necesarias para lograr una suma de pares igual a X. Y finalmente devolver los números mínimos de reemplazo de todas las operaciones. 

Tiempo Complejidad : O (N * K)  
Espacio Auxiliar : O (1)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante las siguientes observaciones:

• X claramente puede tomar valores en el rango [2, 2 * K] .
• Considerando los pares arr[i] y arr[N – i – 1] , se puede observar que la suma de cualquier par puede hacerse igual a X en 0, 1 o 2 sustituciones.
• Sea mx el máximo de estos dos números y mn el mínimo . En un reemplazo, la suma de este par estará en el rango [mn + 1, mx + K] .
• El par para el cual mx es menor que (X – K) y mn es mayor o igual que X necesitará 2 reemplazos.
• Simplemente inserte mx y mn para todos los pares en dos vectores diferentes, ordénelos y aplique la búsqueda binaria para encontrar el número de pares para los que se requieren 2 reemplazos.
• Encuentre los pares que no necesitan ningún reemplazo utilizando Map almacenando las frecuencias de cada suma.
• Finalmente, el número de pares que requieren un reemplazo se puede calcular mediante la ecuación (N / 2 – (pares que necesitan 2 reemplazos + pares que no necesitan reemplazo)) .

Siga estos pasos para encontrar la solución al problema: 

1. Encuentre el máximo y el mínimo para todos los pares arr [ i ] , arr [ N – i – 1 ] y guárdelos en los vectores max_values ​​y min_values ​​respectivamente. También almacene las frecuencias de la suma de todos esos pares en un mapa.
2. Ordene los vectores max_values ​​y min_values.
3. Iterar de X = 2 a X = 2 * K , y para cada valor de X encontrar el número total de reemplazos como se describe en el enfoque anterior. Actualice la respuesta como:

 respuesta = min (respuesta, 2 * (número de pares para los que necesitamos hacer 2 reemplazos) + (número de pares para los que necesitamos hacer un reemplazo)).

Ilustración: 
arr[] = { 1, 2, 2, 1 }, K = 3
max_values ​​= {1, 2} 
min_values ​​= {1, 2} 
map = {{2, 1}, {4, 1}}
en X = 4, se requiere un reemplazo mínimo, es decir, solo se requiere 1 reemplazo, ya sea la conversión de arr[0] a 3 o arr[3] a 3, para que la suma de todos los pares sea igual a 4.

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

// C++ Program to implement the
// above approach
#include <bits/stdc++.h>
#define int long long int
using namespace std;
 
const int inf = 1e18;
 
// Function to find the minimum
// replacements required
int minimumReplacement(int* arr, int N,
                    int K)
{
    int ans = inf;
 
    // Stores the maximum and minimum
    // values for every pair of
    // the form arr[i], arr[n-i-1]
    vector<int> max_values;
    vector<int> min_values;
 
    // Map for storing frequencies
    // of every sum formed by pairs
    map<int, int> sum_equal_to_x;
 
    for (int i = 0; i < N / 2; i++) {
 
        // Minimum element in the pair
        int mn = min(arr[i], arr[N - i - 1]);
 
        // Maximum element in the pair
        int mx = max(arr[i], arr[N - i - 1]);
 
        // Incrementing the frequency of
        // sum encountered
        sum_equal_to_x[arr[i]
                    + arr[N - i - 1]]++;
 
        // Insert minimum and maximum values
        min_values.push_back(mn);
        max_values.push_back(mx);
    }
 
    // Sorting the vectors
    sort(max_values.begin(),
        max_values.end());
 
    sort(min_values.begin(),
        min_values.end());
 
    // Iterate over all possible values of x
    for (int x = 2; x <= 2 * K; x++) {
 
        // Count of pairs for which x > x + k
        int mp1
            = lower_bound(max_values.begin(),
                        max_values.end(), x - K)
            - max_values.begin();
 
        // Count of pairs for which x < mn + 1
        int mp2
            = lower_bound(min_values.begin(),
                        min_values.end(), x)
            - min_values.begin();
 
        // Count of pairs requiring 2 replacements
        int rep2 = mp1 + (N / 2 - mp2);
 
        // Count of pairs requiring no replacements
        int rep0 = sum_equal_to_x[x];
 
        // Count of pairs requiring 1 replacement
        int rep1 = (N / 2 - rep2 - rep0);
 
        // Update the answer
        ans = min(ans, rep2 * 2 + rep1);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int32_t main()
{
    int N = 4;
    int K = 3;
    int arr[] = { 1, 2, 2, 1 };
 
    cout << minimumReplacement(arr, N, K);
    return 0;
}

// Java program implement
// the above approach
import java.util.*;
import java.io.*;
 
class GFG{
     
static int inf = (int)1e18;
 
// Function to find the minimum
// replacements required
static int minimumReplacement(int[] arr, int N,
                                        int K)
{
    int ans = inf;
 
    // Stores the maximum and minimum
    // values for every pair of
    // the form arr[i], arr[n-i-1]
    ArrayList<Integer> max_values = new ArrayList<>();
    ArrayList<Integer> min_values = new ArrayList<>();
 
    // Map for storing frequencies
    // of every sum formed by pairs
    Map<Integer,
        Integer> sum_equal_to_x = new HashMap<>();
 
    for(int i = 0; i < N / 2; i++)
    {
 
        // Minimum element in the pair
        int mn = Math.min(arr[i], arr[N - i - 1]);
 
        // Maximum element in the pair
        int mx = Math.max(arr[i], arr[N - i - 1]);
 
        // Incrementing the frequency of
        // sum encountered
        sum_equal_to_x.put(arr[i] +
                        arr[N - i - 1],
        sum_equal_to_x.getOrDefault(arr[i] +
                                    arr[N - i - 1],
                                    0) + 1);
 
        // Insert minimum and maximum values
        min_values.add(mn);
        max_values.add(mx);
    }
 
    // Sorting the vectors
    Collections.sort(max_values);
 
    Collections.sort(min_values);
 
    // Iterate over all possible values of x
    for(int x = 2; x <= 2 * K; x++)
    {
 
        // Count of pairs for which x > x + k
        int mp1 = max_values.indexOf(x - K);
         
        // Count of pairs for which x < mn + 1
        int mp2 = min_values.indexOf(x);
 
        // Count of pairs requiring 2 replacements
        int rep2 = mp1 + (N / 2 - mp2);
 
        // Count of pairs requiring no replacements
        int rep0 = sum_equal_to_x.getOrDefault(x, -1);
 
        // Count of pairs requiring 1 replacement
        int rep1 = (N / 2 - rep2 - rep0);
 
        // Update the answer
        ans = Math.min(ans, rep2 * 2 + rep1);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    int N = 4;
    int K = 3;
    int arr[] = { 1, 2, 2, 1 };
     
    System.out.print(minimumReplacement(arr, N, K));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement the
# above approach
inf = 10**18
 
def firstOccurance(numbers, length,
                   searchnum):
                        
    answer = -1 
    start = 0   
    end = length - 1
     
    while start <= end:
        middle = (start + end) // 2
         
        if numbers[middle] == searchnum:
            answer = middle
            end = middle - 1
        elif numbers[middle] > searchnum:
            end = middle - 1   
        else:
            start = middle + 1
     
    return answer
  
# Function to find the minimum
# replacements required
def minimumReplacement(arr, N,  K):
 
    ans = inf
  
    # Stores the maximum and minimum
    # values for every pair of
    # the form arr[i], arr[n-i-1]
    max_values = []
    min_values = []
  
    # Map for storing frequencies
    # of every sum formed by pairs
    sum_equal_to_x = dict()
     
    for i in range(N // 2):
  
        # Minimum element in the pair
        mn = min(arr[i], arr[N - i - 1])
  
        # Maximum element in the pair
        mx = max(arr[i], arr[N - i - 1])
  
        # Incrementing the frequency of
        # sum encountered
        if(arr[i] + arr[N - i - 1] not in sum_equal_to_x):
            sum_equal_to_x[arr[i] + arr[N - i - 1]] = 0
             
        sum_equal_to_x[arr[i] + arr[N - i - 1]] += 1
  
        # Insert minimum and maximum values
        min_values.append(mn)
        max_values.append(mx)
     
    max_values.sort()
    min_values.sort()
  
    # Iterate over all possible values of x
    for x in range(2, 2 * K + 1):
  
        # Count of pairs for which x > x + k
        mp1 = firstOccurance(
            max_values, len(max_values), x - K)
  
        # Count of pairs for which x < mn + 1
        mp2 = firstOccurance(
            min_values, len(min_values), x)
  
        # Count of pairs requiring 2 replacements
        rep2 = mp1 + (N // 2 - mp2)
  
        # Count of pairs requiring no replacements
        if x in sum_equal_to_x:
            rep0 = sum_equal_to_x[x]
        else:
            rep0 = 0
  
        # Count of pairs requiring 1 replacement
        rep1 = (N // 2 - rep2 - rep0)
  
        # Update the answer
        ans = min(ans, rep2 * 2 + rep1)
     
    # Return the answer
    return ans
 
# Driver Code
if __name__=='__main__':
     
    N = 4
    K = 3
    arr = [ 1, 2, 2, 1 ]
  
    print(minimumReplacement(arr, N, K))
     
# This code is contributed by pratham76

// C# program implement
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the minimum
// replacements required
static int minimumReplacement(int[] arr, int N,
                                         int K)
{
    int ans = int.MaxValue;
 
    // Stores the maximum and minimum
    // values for every pair of
    // the form arr[i], arr[n-i-1]
    ArrayList max_values = new ArrayList();
    ArrayList min_values = new ArrayList();
 
    // Map for storing frequencies
    // of every sum formed by pairs
    Dictionary<int,
               int> sum_equal_to_x = new Dictionary<int,
                                                    int>();
 
    for(int i = 0; i < N / 2; i++)
    {
         
        // Minimum element in the pair
        int mn = Math.Min(arr[i], arr[N - i - 1]);
 
        // Maximum element in the pair
        int mx = Math.Max(arr[i], arr[N - i - 1]);
 
        // Incrementing the frequency of
        // sum encountered
        sum_equal_to_x[arr[i] + arr[N - i - 1]] =
        sum_equal_to_x.GetValueOrDefault(arr[i] +
                             arr[N - i - 1], 0) + 1;
 
        // Insert minimum and maximum values
        min_values.Add(mn);
        max_values.Add(mx);
    }
 
    // Sorting the vectors
    max_values.Sort();
 
    min_values.Sort();
 
    // Iterate over all possible values of x
    for(int x = 2; x <= 2 * K; x++)
    {
         
        // Count of pairs for which x > x + k
        int mp1 = max_values.IndexOf(x - K);
         
        // Count of pairs for which x < mn + 1
        int mp2 = min_values.IndexOf(x);
 
        // Count of pairs requiring 2 replacements
        int rep2 = mp1 + (N / 2 - mp2);
 
        // Count of pairs requiring no replacements
        int rep0 = sum_equal_to_x.GetValueOrDefault(
                   x, -1);
 
        // Count of pairs requiring 1 replacement
        int rep1 = (N / 2 - rep2 - rep0);
 
        // Update the answer
        ans = Math.Min(ans, rep2 * 2 + rep1);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(string[] args)
{
    int N = 4;
    int K = 3;
    int []arr = { 1, 2, 2, 1 };
     
    Console.Write(minimumReplacement(arr, N, K));
}
}
 
// This code is contributed by rutvik_56

<script>
// JavaScript program to implement the
// above approach
const inf = 10**18
 
function firstOccurance(numbers, length, searchnum)
{
                         
    let answer = -1
    let start = 0
    let end = length - 1
     
    while(start <= end){
        let middle = Math.floor((start + end)/2)
         
        if(numbers[middle] == searchnum){
            answer = middle
            end = middle - 1
        }
        else if(numbers[middle] > searchnum)
            end = middle - 1
        else
            start = middle + 1
    }
     
    return answer
}
 
// Function to find the minimum
// replacements required
function minimumReplacement(arr, N, K){
 
    let ans = inf
 
    // Stores the maximum and minimum
    // values for every pair of
    // the form arr[i], arr[n-i-1]
    let max_values = []
    let min_values = []
 
    // Map for storing frequencies
    // of every sum formed by pairs
    let sum_equal_to_x = new Map()
     
    for(let i=0;i<Math.floor(N / 2);i++){
 
        // Minimum element in the pair
        let mn = Math.min(arr[i], arr[N - i - 1])
 
        // Maximum element in the pair
        let mx = Math.max(arr[i], arr[N - i - 1])
 
        // Incrementing the frequency of
        // sum encountered
        if(sum_equal_to_x.has(arr[i] + arr[N - i - 1])==false)
            sum_equal_to_x.set(arr[i] + arr[N - i - 1],0)
             
        sum_equal_to_x.set(arr[i] + arr[N - i - 1],
        sum_equal_to_x.get(arr[i] + arr[N - i -1])+1)
 
        // Insert minimum and maximum values
        min_values.push(mn)
        max_values.push(mx)
    }
     
    max_values.sort()
    min_values.sort()
 
    // Iterate over all possible values of x
    for(let x=2;x<2 * K + 1;x++){
 
        // Count of pairs for which x > x + k
        let mp1 = firstOccurance(max_values, max_values.length, x - K)
 
        // Count of pairs for which x < mn + 1
        let mp2 = firstOccurance(min_values, min_values.length, x)
 
        // Count of pairs requiring 2 replacements
        rep2 = mp1 + (Math.floor(N / 2) - mp2)
 
        // Count of pairs requiring no replacements
        if(sum_equal_to_x.has(x)){
            rep0 = sum_equal_to_x.get(x)
        }
        else
            rep0 = 0
 
        // Count of pairs requiring 1 replacement
        rep1 = Math.floor(N /2) - rep2 - rep0
 
        // Update the answer
        ans = Math.min(ans, rep2 * 2 + rep1)
    }
     
    // Return the answer
    return ans
}
 
// Driver Code
     
let N = 4
let K = 3
let arr = [ 1, 2, 2, 1 ]
 
document.write(minimumReplacement(arr, N, K))
     
// This code is contributed by shinjanpatra
 
</script>

1

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