Dada una array arr[] que consta de N enteros, la tarea es encontrar el número mínimo de incrementos/decrementos en 1 que se requiere realizar en los elementos de la array para hacer que todos los elementos de la array dada arr[] estén en AP . Si no es posible hacer la array en AP, imprima «-1» .
Ejemplos:
Entrada: arr[] = {19, 16, 9, 5, 0}
Salida: 3
Explicación:
El siguiente es el orden de incremento/decremento de los elementos de la array:
- Incrementa el elemento de array arr[0](= 19) en 1.
- Decrementa el elemento de la array arr[1](= 16) en 1.
- Incrementa el elemento de array arr[2](= 9) en 1.
Después de las operaciones anteriores, la array arr[] se modifica a {20, 15, 10, 5, 0}, que está en AP con el primer término 20 y la diferencia común -5. Por lo tanto, la cuenta total del elemento es 3.
Entrada: arr[] = {1, 2, 3, 4, 10}
Salida: -1
Enfoque: el problema dado se puede resolver encontrando el primer término y la diferencia común de los dos primeros elementos y luego verificar si todos los elementos se pueden cambiar a la secuencia AP con el primer término dado y la diferencia común simplemente iterando sobre la array . Siga los pasos a continuación para resolver el problema:
- Si N es menor que igual a 2 , imprima 0 , porque cada secuencia es una progresión aritmética .
- Inicialice una variable, digamos, res como N + 1 para almacenar la respuesta.
- Iterar en el rango [-1, 1] usando la variable a y realizar los siguientes pasos:
- Iterar en el rango [-1, 1] usando la variable b y realizar los siguientes pasos:
- Inicialice una variable, digamos cambios como 0 para almacenar el recuento de elementos modificados de la array arr[].
- Si a no es igual a 0 , aumente el valor de los cambios en 1 .
- Si b no es igual a 0 , aumente el valor de los cambios en 1 .
- Inicialice una variable, por ejemplo, orig como arr[0] + a para almacenar el primer elemento y diff como (arr[1] + b) – (arr[0] + a) para almacenar la diferencia común de la progresión aritmética .
- Inicialice una variable, digamos, buena como verdadera para almacenar si la secuencia de progresión aritmética con el primer término orig y la diferencia común diff es posible o no.
- Iterar en el rango [2, N-1] usando la variable i y realizar los siguientes pasos:
- Inicialice una variable real como orig+i*diff para almacenar el elemento real de la progresión aritmética en el índice i .
- Si abs(actual – arr[i]) es mayor que 1 , entonces dicha progresión aritmética es inalcanzable. Luego establezca el valor de bueno en falso y rompa el bucle.
- De lo contrario, si actual no es igual a arr[i], aumente el valor de los cambios en 1 .
- Después de recorrer el bucle for interno , actualice el valor de res a min(changes, res).
- Iterar en el rango [-1, 1] usando la variable b y realizar los siguientes pasos:
- Después de completar los pasos anteriores, si res es mayor que N , asigne -1 a res . De lo contrario, imprima el valor de res como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of elements to be changed to convert
// the array into an AP
int findMinimumMoves(int N, int arr[])
{
// If N is less than 3
if (N <= 2) {
return 0;
}
// Stores the answer
int res = N + 1;
// Iterate in the range [-1, 1]
for (int a = -1; a <= 1; a++) {
// Iterate in the range [-1, 1]
for (int b = -1; b <= 1; b++) {
// Stores the total changes
int changes = 0;
if (a != 0) {
changes++;
}
if (b != 0) {
changes++;
}
// Stores the first element
// of the AP
int orig = (arr[0] + a);
// Stores the common difference
// of the AP
int diff = (arr[1] + b) - (arr[0] + a);
// Stores whether it is
// possible to convert the
// array into AP
bool good = true;
// Iterate in the range [2, N-1]
for (int i = 2; i < N; i++) {
// Stores the ith element
// of the AP
int actual = orig + i * diff;
// If abs(actual-arr[i])
// is greater than 1
if (abs(actual - arr[i]) > 1) {
// Mark as false
good = false;
break;
}
// If actual is not
// equal to arr[i]
if (actual != arr[i])
changes++;
}
if (!good)
continue;
// Update the value of res
res = min(res, changes);
}
}
// If res is greater than N
if (res > N)
res = -1;
// Return the value of res
return res;
}
// Driver Code
int main()
{
int arr[] = { 19, 16, 9, 5, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMinimumMoves(N, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the minimum number
// of elements to be changed to convert
// the array into an AP
static int findMinimumMoves(int N, int arr[])
{
// If N is less than 3
if (N <= 2)
{
return 0;
}
// Stores the answer
int res = N + 1;
// Iterate in the range [-1, 1]
for(int a = -1; a <= 1; a++)
{
// Iterate in the range [-1, 1]
for(int b = -1; b <= 1; b++)
{
// Stores the total changes
int changes = 0;
if (a != 0)
{
changes++;
}
if (b != 0)
{
changes++;
}
// Stores the first element
// of the AP
int orig = (arr[0] + a);
// Stores the common difference
// of the AP
int diff = (arr[1] + b) - (arr[0] + a);
// Stores whether it is
// possible to convert the
// array into AP
boolean good = true;
// Iterate in the range [2, N-1]
for(int i = 2; i < N; i++)
{
// Stores the ith element
// of the AP
int actual = orig + i * diff;
// If abs(actual-arr[i])
// is greater than 1
if (Math.abs(actual - arr[i]) > 1)
{
// Mark as false
good = false;
break;
}
// If actual is not
// equal to arr[i]
if (actual != arr[i])
changes++;
}
if (!good)
continue;
// Update the value of res
res = Math.min(res, changes);
}
}
// If res is greater than N
if (res > N)
res = -1;
// Return the value of res
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 19, 16, 9, 5, 0 };
int N = arr.length;
System.out.println(findMinimumMoves(N, arr));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program for the above approach # Function to find the minimum number # of elements to be changed to convert # the array into an AP def findMinimumMoves(N, arr): # If N is less than 3 if (N <= 2): return 0 # Stores the answer res = N + 1 # Iterate in the range [-1, 1] for a in range(-1, 2, 1): # Iterate in the range [-1, 1] for b in range(-1, 2, 1): # Stores the total changes changes = 0 if (a != 0): changes += 1 if (b != 0): changes += 1 # Stores the first element # of the AP orig = (arr[0] + a) # Stores the common difference # of the AP diff = (arr[1] + b) - (arr[0] + a) # Stores whether it is # possible to convert the # array into AP good = True # Iterate in the range [2, N-1] for i in range(2, N, 1): # Stores the ith element # of the AP actual = orig + i * diff # If abs(actual-arr[i]) # is greater than 1 if (abs(actual - arr[i]) > 1): # Mark as false good = False break # If actual is not # equal to arr[i] if (actual != arr[i]): changes += 1 if (good == False): continue # Update the value of res res = min(res, changes) # If res is greater than N if (res > N): res = -1 # Return the value of res return res # Driver Code if __name__ == '__main__': arr = [ 19, 16, 9, 5, 0 ] N = len(arr) print(findMinimumMoves(N, arr)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of elements to be changed to convert
// the array into an AP
static int findMinimumMoves(int N, int[] arr)
{
// If N is less than 3
if (N <= 2)
{
return 0;
}
// Stores the answer
int res = N + 1;
// Iterate in the range [-1, 1]
for(int a = -1; a <= 1; a++)
{
// Iterate in the range [-1, 1]
for(int b = -1; b <= 1; b++)
{
// Stores the total changes
int changes = 0;
if (a != 0)
{
changes++;
}
if (b != 0)
{
changes++;
}
// Stores the first element
// of the AP
int orig = (arr[0] + a);
// Stores the common difference
// of the AP
int diff = (arr[1] + b) - (arr[0] + a);
// Stores whether it is
// possible to convert the
// array into AP
bool good = true;
// Iterate in the range [2, N-1]
for(int i = 2; i < N; i++)
{
// Stores the ith element
// of the AP
int actual = orig + i * diff;
// If abs(actual-arr[i])
// is greater than 1
if (Math.Abs(actual - arr[i]) > 1)
{
// Mark as false
good = false;
break;
}
// If actual is not
// equal to arr[i]
if (actual != arr[i])
changes++;
}
if (!good)
continue;
// Update the value of res
res = Math.Min(res, changes);
}
}
// If res is greater than N
if (res > N)
res = -1;
// Return the value of res
return res;
}
// Driver code
static public void Main()
{
int[] arr = { 19, 16, 9, 5, 0 };
int N = arr.Length;
Console.WriteLine(findMinimumMoves(N, arr));
}
}
// This code is contributed by target_2.
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// of elements to be changed to convert
// the array into an AP
function findMinimumMoves(N, arr)
{
// If N is less than 3
if (N <= 2)
{
return 0;
}
// Stores the answer
let res = N + 1;
// Iterate in the range [-1, 1]
for(let a = -1; a <= 1; a++)
{
// Iterate in the range [-1, 1]
for(let b = -1; b <= 1; b++)
{
// Stores the total changes
let changes = 0;
if (a != 0)
{
changes++;
}
if (b != 0)
{
changes++;
}
// Stores the first element
// of the AP
let orig = (arr[0] + a);
// Stores the common difference
// of the AP
let diff = (arr[1] + b) - (arr[0] + a);
// Stores whether it is
// possible to convert the
// array into AP
let good = true;
// Iterate in the range [2, N-1]
for(let i = 2; i < N; i++)
{
// Stores the ith element
// of the AP
let actual = orig + i * diff;
// If abs(actual-arr[i])
// is greater than 1
if (Math.abs(actual - arr[i]) > 1)
{
// Mark as false
good = false;
break;
}
// If actual is not
// equal to arr[i]
if (actual != arr[i])
changes++;
}
if (!good)
continue;
// Update the value of res
res = Math.min(res, changes);
}
}
// If res is greater than N
if (res > N)
res = -1;
// Return the value of res
return res;
}
// Driver Code
let arr = [ 19, 16, 9, 5, 0 ];
let N = arr.length;
document.write(findMinimumMoves(N, arr));
// This code is contributed by target_2
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA