Convierta la array dada en Progresión aritmética agregando un elemento

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

Deja una respuesta

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