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++
// 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
// 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
# 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#
// 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.
Javascript
<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 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anilyogi2801 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA