Reemplazos mínimos con números reales requeridos para hacer Array AP dado

Dada una array arr[] de N enteros. La tarea es convertir la array en una progresión aritmética con el mínimo número de reemplazos posible. En un reemplazo, cualquier elemento puede ser reemplazado por cualquier número real .

Ejemplos:

Entrada: N = 6, arr[] = { 3, -2, 4, -1, -4, 0 }
Salida: 3
Explicación: Cambiar arr[0] = -2.5, arr[2] = -1.5, arr[ 4] = -0.5
Entonces, la nueva secuencia es AP { -2.5, -2, -1.5, -1, -0.5, 0} con 0.5 como diferencia común.

Entrada: N = 5, arr[] = { 1, 0, 2, 4, 5}
Salida: 2
Explicación: Cambiar arr[1] = 2, arr[2] = 3
Entonces, la nueva secuencia es { 1, 2 , 3, 4, 5 } que es un AP.

Enfoque: La solución del problema se basa en encontrar todas las diferencias comunes posibles de la array. Siga los pasos que se mencionan a continuación:

• Ejecute un ciclo anidado para encontrar todas las diferencias comunes posibles de la array donde solo se forman dos elementos y AP y guárdelos en un mapa .
• Ahora, para cada diferencia común, recorra la array y descubra el número total de valores que se encuentran en el AP con esa diferencia específica.
• El número restante de valores debe cambiarse.
• El mínimo entre estos valores restantes es la respuesta requerida.

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

// C++ program to find the minimum number
// of changes required to make the given
// array an AP
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of changes required to make the given
// array an AP
int minChanges(int arr[], int N)
{
    if (N <= 2) {
        return 0;
    }
 
    int ans = INT_MAX;
 
    for (int i = 0; i < N; i++) {
 
        // Map to store number of points
        // that lie on the Ap
        // with key as the common difference
        unordered_map<double, int> points;
 
        for (int j = 0; j < N; j++) {
            if (i == j)
                continue;
 
            // Calculating the common difference
            // for the AP with arr[i] and arr[j]
            double slope
                = (double)(arr[j] - arr[i]) / (j - i);
            points[slope]++;
        }
 
        int max_points = INT_MIN;
 
        // Finding maximum number of values
        // that lie on the Ap
        for (auto point : points) {
            max_points = max(max_points,
                             point.second);
        }
        max_points++;
        ans = min(ans, N - max_points);
    }
    return ans;
}
 
// Driver code
int main()
{
    int N = 6;
    int arr[] = { 3, -2, 4, -1, -4, 0 };
 
    // Function call
    cout << minChanges(arr, N);
    return 0;
}

// JAVA program to find the minimum number
// of changes required to make the given
// array an AP
import java.util.*;
class GFG
{
 
  // Function to find the minimum number
  // of changes required to make the given
  // array an AP
  public static int minChanges(int[] arr, int N)
  {
    if (N <= 2) {
      return 0;
    }
 
    int ans = Integer.MAX_VALUE;
 
    for (int i = 0; i < N; i++) {
 
      // Map to store number of points
      // that lie on the Ap
      // with key as the common difference
      HashMap<Double, Integer> points
        = new HashMap<>();
 
      for (int j = 0; j < N; j++) {
        if (i == j)
          continue;
 
        // Calculating the common difference
        // for the AP with arr[i] and arr[j]
        double slope
          = (double)(arr[j] - arr[i]) / (j - i);
        if (points.containsKey(slope)) {
          points.put(slope,
                     points.get(slope) + 1);
        }
        else {
          points.put(slope, 1);
        }
      }
 
      int max_points = Integer.MIN_VALUE;
 
      // Finding maximum number of values
      // that lie on the Ap
      for (Map.Entry<Double, Integer> mp :
           points.entrySet()) {
        max_points
          = Math.max(max_points, mp.getValue());
      }
      max_points++;
      ans = Math.min(ans, N - max_points);
    }
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 6;
    int[] arr = new int[] { 3, -2, 4, -1, -4, 0 };
 
    // Function call
    System.out.print(minChanges(arr, N));
  }
}
 
// This code is contributed by Taranpreet

# Python3 program to find the minimum number
# of changes required to make the given array an AP.
def minChanges(arr, n):
    if n <= 2:
        return 0
    ans = float('inf')
    for i in range(n):
       
        # Map to store number of points
        # that lie on the Ap
        # with key as the common difference
        points = {}
        for j in range(n):
            if i == j:
                continue
                 
            # Calculating the common difference
            # for the AP with arr[i] and arr[j] double slope
            slope = (arr[j] - arr[i])//(j - i)
            if slope in points:
                points[slope] += 1
            else:
                points[slope] = 1
    max_points = float('-inf')
     
    # Finding maximum number of values
    # that lie on the Ap
    for point in points:
        max_points = max(max_points, points[point])
    max_points += 1
    ans = min(ans, n-max_points)
    return ans
   
# Driver code
n = 6
arr = [3, -2, 4, -1, -4, 0]
print(minChanges(arr, n))
'''This code is written by Rajat Kumar (GLA University)'''

// C# program to find the minimum number
// of changes required to make the given
// array an AP
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find the minimum number
  // of changes required to make the given
  // array an AP
  static int minChanges(int[] arr, int N)
  {
    if (N <= 2) {
      return 0;
    }
 
    int ans = Int32.MaxValue;
 
    for (int i = 0; i < N; i++) {
 
      // Map to store number of points
      // that lie on the Ap
      // with key as the common difference
      Dictionary<double, int> points
        = new Dictionary<double, int>();
 
      for (int j = 0; j < N; j++) {
        if (i == j)
          continue;
 
        // Calculating the common difference
        // for the AP with arr[i] and arr[j]
        double slope
          = (double)(arr[j] - arr[i]) / (j - i);
        if (!points.ContainsKey(slope)) {
          points.Add(slope, 1);
        }
        else {
          points[slope] = points[slope] + 1;
        }
      }
 
      int max_points = Int32.MinValue;
 
      // Finding maximum number of values
      // that lie on the Ap
      foreach(
        KeyValuePair<double, int> point in points)
      {
        max_points
          = Math.Max(max_points, point.Value);
      }
      max_points++;
      ans = Math.Min(ans, N - max_points);
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 6;
    int[] arr = { 3, -2, 4, -1, -4, 0 };
 
    // Function call
    Console.Write(minChanges(arr, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find the minimum number
       // of changes required to make the given
       // array an AP
       function minChanges(arr, N)
       {
           if (N <= 2)
           {
               return 0;
           }
 
           let ans = Number.MAX_VALUE;
 
           for (let i = 0; i < N; i++) {
 
               // Map to store number of points
               // that lie on the Ap
               // with key as the common difference
               let points = new Map();
 
               for (let j = 0; j < N; j++) {
                   if (i == j)
                       continue;
 
                   // Calculating the common difference
                   // for the AP with arr[i] and arr[j]
                   let slope
                       = (arr[j] - arr[i]) / (j - i);
                   if (!points.has(slope))
                       points.set(slope, 1);
                   else {
                       points.set(slope, points.get(slope) + 1)
                   }
               }
 
               let max_points = Number.MIN_VALUE;
 
               // Finding maximum number of values
               // that lie on the Ap
               for (let [key, val] of points) {
                   max_points = Math.max(max_points,
                       val);
               }
               max_points++;
               ans = Math.min(ans, N - max_points);
           }
           return ans;
       }
 
       // Driver code
       let N = 6;
       let arr = [3, -2, 4, -1, -4, 0];
 
       // Function call
       document.write(minChanges(arr, N));
 
      // This code is contributed by Potta Lokesh
   </script>

3

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)