Dada una array que es una progresión aritmética original con un elemento modificado. La tarea es volver a convertirlo en una progresión aritmética. Si hay muchas secuencias posibles, devuelva cualquiera de ellas. La longitud de la array siempre será mayor que 2. Ejemplos:
Entrada: arr = [1, 3, 4, 7] Salida: arr = [1, 3, 5, 7] La diferencia común para la progresión aritmética es 2, por lo que la progresión aritmética resultante es [1, 3, 5, 7 ]. Entrada: arr = [1, 3, 7] Salida: arr = [-1, 3, 7] La diferencia común puede ser 2, 3 o 4. Por lo tanto, la array resultante puede ser [1, 3, 5], [-1, 3, 7] o [1, 4, 7]. Como se puede elegir cualquiera, [-1, 3, 7] se devuelve como salida.
Enfoque: Los componentes clave de una progresión aritmética son el término inicial y la diferencia común. Así que nuestra tarea es encontrar estos dos valores para conocer la progresión aritmética real.
- Si la longitud de la array es 3, tome la diferencia común como la diferencia entre dos elementos cualesquiera.
- De lo contrario, intente encontrar la diferencia común utilizando los primeros cuatro elementos.
- Comprueba si los primeros tres elementos están en progresión aritmética usando la fórmula a[1] – a[0] = a[2] – a[1]. Si están en progresión aritmética, la diferencia común d = a[1] – a[0] y el término inicial sería a[0]
- Comprueba si los elementos 2, 3 y 4 están en progresión aritmética usando la fórmula a[2] – a[1] = a[3] – a[2]. Si están en progresión aritmética, la diferencia común d = a[2] – a[1], lo que significa que el primer elemento ha sido cambiado, entonces el término inicial es a[0] = a[1] – d
- En los dos casos anteriores, hemos comprobado si se ha cambiado el primer elemento o el cuarto elemento. Si ambos casos son falsos, significa que el primer o cuarto elemento no se modificó. Entonces la diferencia común se puede tomar como d = (a[3] – a[0])/3 y el término inicial = a[0]
- Imprime todos los elementos usando el término inicial y la diferencia común.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to change one element of an array such
// that the resulting array is in arithmetic progression.
#include <bits/stdc++.h>
using namespace std;
// Finds the initial term and common difference and
// prints the resulting sequence.
void makeAP(int arr[], int n)
{
int initial_term, common_difference;
if (n == 3) {
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else if ((arr[1] - arr[0]) == arr[2] - arr[1]) {
// Check if the first three elements are in
// arithmetic progression
initial_term = arr[0];
common_difference = arr[1] - arr[0];
}
else if ((arr[2] - arr[1]) == (arr[3] - arr[2])) {
// Check if the first element is not
// in arithmetic progression
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else {
// The first and fourth element are
// in arithmetic progression
common_difference = (arr[3] - arr[0]) / 3;
initial_term = arr[0];
}
// Print the arithmetic progression
for (int i = 0; i < n; i++)
cout << initial_term + (i * common_difference) << " ";
cout << endl;
}
// Driver Program
int main()
{
int arr[] = { 1, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
makeAP(arr, n);
return 0;
}
Java
// Java program to change one element of an array such
// that the resulting array is in arithmetic progression.
import java.util.Arrays;
class AP {
static void makeAP(int arr[], int n)
{
int initial_term, common_difference;
// Finds the initial term and common difference and
// prints the resulting array.
if (n == 3) {
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else if ((arr[1] - arr[0]) == arr[2] - arr[1]) {
// Check if the first three elements are in
// arithmetic progression
initial_term = arr[0];
common_difference = arr[1] - arr[0];
}
else if ((arr[2] - arr[1]) == (arr[3] - arr[2])) {
// Check if the first element is not
// in arithmetic progression
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else {
// The first and fourth element are
// in arithmetic progression
common_difference = (arr[3] - arr[0]) / 3;
initial_term = arr[0];
}
// Print the arithmetic progression
for (int i = 0; i < n; i++)
System.out.print(initial_term +
(i * common_difference) + " ");
System.out.println();
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 7 };
int n = arr.length;
makeAP(arr, n);
}
}
Python3
# Python program to change one element of an array such # that the resulting array is in arithmetic progression. def makeAP(arr, n): initial_term, common_difference = 0, 0 if (n == 3): common_difference = arr[2] - arr[1] initial_term = arr[1] - common_difference elif((arr[1] - arr[0]) == arr[2] - arr[1]): # Check if the first three elements are in # arithmetic progression initial_term = arr[0] common_difference = arr[1] - arr[0] elif((arr[2] - arr[1]) == (arr[3] - arr[2])): # Check if the first element is not # in arithmetic progression common_difference = arr[2] - arr[1] initial_term = arr[1] - common_difference else: # The first and fourth element are # in arithmetic progression common_difference = (arr[3] - arr[0]) / 3 initial_term = arr[0] # Print the arithmetic progression for i in range(n): print(int(initial_term+ (i * common_difference)), end = " ") print() # Driver code arr = [1, 3, 7] n = len(arr) makeAP(arr, n)
C#
// C# program to change one element of an array such
// that the resulting array is in arithmetic progression.
using System;
public class AP
{
static void makeAP(int []arr, int n)
{
int initial_term, common_difference;
// Finds the initial term and common difference and
// prints the resulting array.
if (n == 3)
{
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else if ((arr[1] - arr[0]) == arr[2] - arr[1])
{
// Check if the first three elements are in
// arithmetic progression
initial_term = arr[0];
common_difference = arr[1] - arr[0];
}
else if ((arr[2] - arr[1]) == (arr[3] - arr[2]))
{
// Check if the first element is not
// in arithmetic progression
common_difference = arr[2] - arr[1];
initial_term = arr[1] - common_difference;
}
else
{
// The first and fourth element are
// in arithmetic progression
common_difference = (arr[3] - arr[0]) / 3;
initial_term = arr[0];
}
// Print the arithmetic progression
for (int i = 0; i < n; i++)
Console.Write(initial_term +
(i * common_difference) + " ");
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 3, 7 };
int n = arr.Length;
makeAP(arr, n);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to change one element of an array such
// that the resulting array is in arithmetic progression.
function makeAP(arr, n){
let initial_term = 0, common_difference = 0
if (n == 3){
common_difference = arr[2] - arr[1]
initial_term = arr[1] - common_difference
}
else if((arr[1] - arr[0]) == arr[2] - arr[1]){
// Check if the first three elements are in
// arithmetic progression
initial_term = arr[0]
common_difference = arr[1] - arr[0]
}
else if((arr[2] - arr[1]) == (arr[3] - arr[2])){
// Check if the first element is not
// in arithmetic progression
common_difference = arr[2] - arr[1]
initial_term = arr[1] - common_difference
}
else{
// The first and fourth element are
// in arithmetic progression
common_difference = Math.floor((arr[3] - arr[0]) / 3)
initial_term = arr[0]
}
// Print the arithmetic progression
for(let i=0;i<n;i++){
document.write(initial_term+(i * common_difference)," ")
}
document.write("</br>")
}
// Driver code
let arr = [1, 3, 7]
let n = arr.length
makeAP(arr, n)
// This code is contributed by shinjanpatra
</script>
Producción:
-1 3 7
Complejidad de tiempo : O(N), donde N es el número de elementos en la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kanakalathav99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA