Dada una array arr[] de 
enteros y un número 
. Puede cambiar cualquier elemento de la array a un número entero. La tarea es encontrar el número mínimo de cambios requeridos para hacer que la array dada sea una progresión aritmética con la diferencia común .
Ejemplos :
Input : N = 4, d = 2
arr[] = {1, 2, 4, 6}
Output : 1
Explanation: change a[0]=0.
So, new sequence is 0, 2, 4, 6 which is an AP.
Input : N = 5, d = 1
arr[] = {1, 3, 3, 4, 6}
Output : 2
Explanation: change a[1]=2 and a[4]=5.
So, new sequence is 1, 2, 3, 4, 5 which is an AP.
La idea para resolver este problema es observar que las fórmulas para el n-ésimo término en un AP son:
an = a0 + (n-1)*d Where, a0 is the first term and d is the common difference.
Nos dan los valores de 
y a n . Entonces, encontraremos el valor de un 0 para todos los valores de i, donde 1<=i<=n y almacenaremos la frecuencia de aparición de un 0 para diferentes valores de i.
Ahora, el número mínimo de elementos necesarios para cambiar es:
n - (maximum frequency of a0)
Donde la frecuencia máxima de un 0 significa el número total de elementos en la array para los cuales el valor del primer término en el AP es el mismo.
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 with common difference d
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of changes required to make the given
// array an AP with common difference d
int minimumChanges(int arr[], int n, int d)
{
int maxFreq = INT_MIN;
// Map to store frequency of a0
unordered_map<int, int> freq;
// storing frequency of a0 for all possible
// values of a[i] and finding the maximum
// frequency
for (int i = 0; i < n; ++i) {
int a0 = arr[i] - (i)*d;
// increment frequency by 1
if (freq.find(a0) != freq.end()) {
freq[a0]++;
}
else
freq.insert(make_pair(a0, 1));
// finds count of most frequent number
if (freq[a0] > maxFreq)
maxFreq = freq[a0];
}
// minimum number of elements needed to
// be changed is: n - (maximum frequency of a0)
return (n - maxFreq);
}
// Driver Program
int main()
{
int n = 5, d = 1;
int arr[] = { 1, 3, 3, 4, 6 };
cout << minimumChanges(arr, n, d);
return 0;
}
Java
// Java program to find the
// minimum number of changes
// required to make the given
// array an AP with common
// difference d
import java.util.*;
class GFG {
// Function to find the minimum
// number of changes required
// to make the given array an
// AP with common difference d
static int minimumChanges(int arr[],
int n, int d)
{
int maxFreq = -1;
// Map to store frequency of a0
HashMap<Integer,
Integer>
freq = new HashMap<Integer,
Integer>();
// storing frequency of a0 for
// all possible values of a[i]
// and finding the maximum
// frequency
for (int i = 0; i < n; ++i) {
int a0 = arr[i] - (i)*d;
// increment frequency by 1
if (freq.containsKey(a0)) {
freq.put(a0, freq.get(a0) + 1);
}
else
freq.put(a0, 1);
// finds count of most
// frequent number
if (freq.get(a0) > maxFreq)
maxFreq = freq.get(a0);
}
// minimum number of elements
// needed to be changed is:
// n - (maximum frequency of a0)
return (n - maxFreq);
}
// Driver Code
public static void main(String args[])
{
int n = 5, d = 1;
int arr[] = { 1, 3, 3, 4, 6 };
System.out.println(minimumChanges(arr, n, d));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to find the minimum
# number of changes required to make
# the given array an AP with common
# difference d
# Function to find the minimum number
# of changes required to make the given
# array an AP with common difference d
def minimumChanges(arr, n, d):
maxFreq = -2147483648
# dictionary to store
# frequency of a0
freq = {}
# storing frequency of a0 for
# all possible values of a[i]
# and finding the maximum'
# frequency
for i in range(n):
a0 = arr[i] - i * d
# increment frequency by 1
if a0 in freq:
freq[a0] += 1
else:
freq[a0] = 1
# finds count of most
# frequent number
if freq[a0] > maxFreq:
maxFreq = freq[a0]
# minimum number of elements
# needed to be changed is:
# n - (maximum frequency of a0)
return (n-maxFreq)
# Driver Code
# number of terms in ap
n = 5
# difference in AP
d = 1
arr = [1, 3, 3, 4, 6 ]
ans = minimumChanges(arr, n, d)
print(ans)
# This code is contributed
# by sahil shelangia
C#
// C# program to find the
// minimum number of changes
// required to make the given
// array an AP with common
// difference d
using System;
using System.Collections.Generic;
class GFG {
// Function to find the minimum
// number of changes required
// to make the given array an
// AP with common difference d
static int minimumChanges(int[] arr,
int n, int d)
{
int maxFreq = -1;
// Map to store frequency of a0
Dictionary<int, int> freq = new Dictionary<int, int>();
// storing frequency of a0 for
// all possible values of a[i]
// and finding the maximum
// frequency
for (int i = 0; i < n; ++i) {
int a0 = arr[i] - (i)*d;
// increment frequency by 1
if (freq.ContainsKey(a0)) {
var obj = freq[a0];
freq.Remove(a0);
freq.Add(a0, obj + 1);
}
else
freq.Add(a0, 1);
// finds count of most
// frequent number
if (freq[a0] > maxFreq)
maxFreq = freq[a0];
}
// minimum number of elements
// needed to be changed is:
// n - (maximum frequency of a0)
return (n - maxFreq);
}
// Driver Code
public static void Main(String[] args)
{
int n = 5, d = 1;
int[] arr = { 1, 3, 3, 4, 6 };
Console.WriteLine(minimumChanges(arr, n, d));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP program to find the minimum number
// of changes required to make the given
// array an AP with common difference d
// Function to find the minimum number
// of changes required to make the given
// array an AP with common difference d
function minimumChanges(&$arr, $n, $d)
{
$maxFreq = PHP_INT_MIN;
// array to store frequency of a0
$freq = array();
// storing frequency of a0 for
// all possible values of a[i]
// and finding the maximum
// frequency
for ($i = 0; $i < $n; ++$i)
{
$a0 = $arr[$i] - ($i) * $d;
// increment frequency by 1
if(array_search($a0, $freq))
{
$freq[$a0]++;
}
else
$freq[$a0] = 1;
// finds count of most
// frequent number
if ($freq[$a0] > $maxFreq)
$maxFreq = $freq[$a0];
}
// minimum number of elements
// needed to be changed is:
// $n - (maximum frequency of a0)
return ($n - $maxFreq);
}
// Driver Code
$n = 5;
$d = 1;
$arr = array( 1, 3, 3, 4, 6 );
echo minimumChanges($arr, $n, $d);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find the
// minimum number of changes
// required to make the given
// array an AP with common
// difference d
// Function to find the minimum
// number of changes required
// to make the given array an
// AP with common difference d
function minimumChanges(arr,n,d)
{
let maxFreq = -1;
// Map to store frequency of a0
let freq = new Map();
// storing frequency of a0 for
// all possible values of a[i]
// and finding the maximum
// frequency
for (let i = 0; i < n; ++i) {
let a0 = arr[i] - (i)*d;
// increment frequency by 1
if (freq.has(a0)) {
freq.set(a0, freq.get(a0) + 1);
}
else
freq.set(a0, 1);
// finds count of most
// frequent number
if (freq.get(a0) > maxFreq)
maxFreq = freq.get(a0);
}
// minimum number of elements
// needed to be changed is:
// n - (maximum frequency of a0)
return (n - maxFreq);
}
// Driver Code
let n = 5, d = 1;
let arr=[ 1, 3, 3, 4, 6];
document.write(minimumChanges(arr, n, d));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA