Dada una array arr[] , la tarea es encontrar un elemento que se pueda agregar a la array para convertirlo en progresión aritmética. Si es imposible convertir la array dada en un AP, imprima -1 .
Ejemplos:
Entrada: arr[] = {3, 7}
Salida: 11
3, 7 y 11 es una secuencia AP finita.Entrada: a[] = {4, 6, 8, 15}
Salida: -1
Acercarse:
- Ordene la array y comience a recorrer la array elemento por elemento y observe la diferencia entre los dos elementos consecutivos.
- Si la diferencia de todos los elementos es la misma, imprima el último elemento + la diferencia común .
- Si la diferencia es diferente para un par como máximo (arr[i – 1], arr[i]) y diff = 2 * diferencia común para todos los demás elementos, entonces imprima arr[i] – diferencia común .
- De lo contrario imprime -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; // Function to return the number to be // added int getNumToAdd(int arr[], int n) { sort(arr,arr+n); int d = arr[1] - arr[0]; int numToAdd = -1; bool numAdded = false; for (int i = 2; i < n; i++) { int diff = arr[i] - arr[i - 1]; // If difference of the current // consecutive elements is // different from the common // difference if (diff != d) { // If number has already been // chosen then it's not possible // to add another number if (numAdded) return -1; // If the current different is // twice the common difference // then a number can be added midway // from current and previous element if (diff == 2 * d) { numToAdd = arr[i] - d; // Number has been chosen numAdded = true; } // It's not possible to maintain // the common difference else return -1; } } // Return last element + common difference // if no element is chosen and the array // is already in AP if (numToAdd == -1) return (arr[n - 1] + d); // Else return the chosen number return numToAdd; } // Driver code int main() { int arr[] = { 1, 3, 5, 7, 11, 13, 15 }; int n = sizeof(arr)/sizeof(arr[0]); cout << getNumToAdd(arr, n); } // This code is contributed // by ihritik
Java
// Java implementation of the approach import java.util.*; public class GFG { // Function to return the number to be // added static int getNumToAdd(int arr[], int n) { Arrays.sort(arr); int d = arr[1] - arr[0]; int numToAdd = -1; boolean numAdded = false; for (int i = 2; i < n; i++) { int diff = arr[i] - arr[i - 1]; // If difference of the current // consecutive elements is // different from the common // difference if (diff != d) { // If number has already been // chosen then it's not possible // to add another number if (numAdded) return -1; // If the current different is // twice the common difference // then a number can be added midway // from current and previous element if (diff == 2 * d) { numToAdd = arr[i] - d; // Number has been chosen numAdded = true; } // It's not possible to maintain // the common difference else return -1; } } // Return last element + common difference // if no element is chosen and the array // is already in AP if (numToAdd == -1) return (arr[n - 1] + d); // Else return the chosen number return numToAdd; } // Driver code public static void main(String[] args) { int arr[] = { 1, 3, 5, 7, 11, 13, 15 }; int n = arr.length; System.out.println(getNumToAdd(arr, n)); } }
Python3
# Python 3 implementation of the approach # Function to return the number # to be added def getNumToAdd(arr, n): arr.sort(reverse = False) d = arr[1] - arr[0] numToAdd = -1 numAdded = False for i in range(2, n, 1): diff = arr[i] - arr[i - 1] # If difference of the current consecutive # elements is different from the common # difference if (diff != d): # If number has already been chosen # then it's not possible to add # another number if (numAdded): return -1 # If the current different is twice # the common difference then a # number can be added midway from # current and previous element if (diff == 2 * d): numToAdd = arr[i] - d # Number has been chosen numAdded = True # It's not possible to maintain # the common difference else: return -1 # Return last element + common difference # if no element is chosen and the array # is already in AP if (numToAdd == -1): return (arr[n - 1] + d) # Else return the chosen number return numToAdd # Driver code if __name__ == '__main__': arr = [1, 3, 5, 7, 11, 13, 15] n = len(arr) print(getNumToAdd(arr, n)) # This code is contributed # mohit kumar 29
C#
// C# implementation of the approach using System; public class GFG { // Function to return the number to be // added static int getNumToAdd(int []arr, int n) { Array.Sort(arr); int d = arr[1] - arr[0]; int numToAdd = -1; bool numAdded = false; for (int i = 2; i < n; i++) { int diff = arr[i] - arr[i - 1]; // If difference of the current // consecutive elements is // different from the common // difference if (diff != d) { // If number has already been // chosen then it's not possible // to add another number if (numAdded) return -1; // If the current different is // twice the common difference // then a number can be added midway // from current and previous element if (diff == 2 * d) { numToAdd = arr[i] - d; // Number has been chosen numAdded = true; } // It's not possible to maintain // the common difference else return -1; } } // Return last element + common difference // if no element is chosen and the array // is already in AP if (numToAdd == -1) return (arr[n - 1] + d); // Else return the chosen number return numToAdd; } // Driver code public static void Main() { int []arr = { 1, 3, 5, 7, 11, 13, 15 }; int n = arr.Length; Console.WriteLine(getNumToAdd(arr, n)); } } // This code is contributed // by ihritik
PHP
<?php // PHP implementation of the approach // Function to return the number // to be added function getNumToAdd($arr, $n) { sort($arr); $d = $arr[1] - $arr[0]; $numToAdd = -1; $numAdded = false; for ($i = 2; $i < $n; $i++) { $diff = $arr[$i] - $arr[$i - 1]; // If difference of the current // consecutive elements is // different from the common // difference if ($diff != $d) { // If number has already been // chosen then it's not possible // to add another number if ($numAdded) return -1; // If the current different is // twice the common difference // then a number can be added midway // from current and previous element if ($diff == 2 * $d) { $numToAdd = $arr[$i] - $d; // Number has been chosen $numAdded = true; } // It's not possible to maintain // the common difference else return -1; } } // Return last element + common difference // if no element is chosen and the array // is already in AP if ($numToAdd == -1) return ($arr[$n - 1] + $d); // Else return the chosen number return $numToAdd; } // Driver code $arr = array( 1, 3, 5, 7, 11, 13, 15 ); $n = sizeof($arr); echo getNumToAdd($arr, $n); // This code is contributed by Sachin.. ?>
Javascript
<script> // Javascript implementation of the approach // Function to return the number to be // added function getNumToAdd(arr, n) { arr.sort(function(a, b){return a - b}); var d = arr[1] - arr[0]; var numToAdd = -1; var numAdded = false; for(var i = 2; i < n; i++) { var diff = arr[i] - arr[i - 1]; // If difference of the current // consecutive elements is // different from the common // difference if (diff != d) { // If number has already been // chosen then it's not possible // to add another number if (numAdded) return -1; // If the current different is // twice the common difference // then a number can be added midway // from current and previous element if (diff == 2 * d) { numToAdd = arr[i] - d; // Number has been chosen numAdded = true; } // It's not possible to maintain // the common difference else return -1; } } // Return last element + common difference // if no element is chosen and the array // is already in AP if (numToAdd == -1) return (arr[n - 1] + d); // Else return the chosen number return numToAdd; } // Driver code var arr = [ 1, 3, 5, 7, 11, 13, 15 ]; var n = arr.length; document.write(getNumToAdd(arr, n)); // This code is contributed by Ankita saini </script>
Producción:
9
Complejidad de tiempo: O (n Log n)
Complejidad espacial : O (1) ya que solo se usa una variable constante
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA