Given an array arr[] of N integers. The task is to convert the array into an Arithmetic Progression with the minimum number of replacements possible. In one replacement any one element can be replaced by any real number.
Examples:
Input: N = 6, arr[] = { 3, -2, 4, -1, -4, 0 }
Output: 3
Explanation: Change arr[0] = -2.5, arr[2] = -1.5, arr[4] = -0.5
So, the new sequence is AP { -2.5, -2, -1.5, -1, -0.5, 0} with 0.5 as the common difference.Input: N = 5, arr[] = { 1, 0, 2, 4, 5}
Output: 2
Explanation: Change arr[1] = 2, arr[2] = 3
So, the new sequence is { 1, 2, 3, 4, 5 } which is an AP.
Approach: The solution of the problem is based on finding the all common differences possible from the array. Follow the steps mentioned below:
- Run a nested loop to find all the possible common differences from the array where only two elements are forming and AP and store them in a map.
- Now for each common difference, traverse the array and find out the total number of values lying in the AP with that specific difference.
- The remaining number of values needs to be changed.
- The minimum among these remaining values is the required answer.
Below is the implementation of the above approach:
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 APint 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 codeint 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 APimport 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 coden = 6arr = [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 APusing 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> |
Output
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
