Número mínimo de cambios requeridos para convertir la array dada en un AP

Dada una array arr[] de  N   enteros y un número  d . 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  d .

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  d   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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *