CareerCup

Solution written in Java and finds missing element in O(log(n)). For more in-depth and unit tests, see github: git.io/vu3iJ .

public static int findMissing( List<Integer> sequence ) {
		
	int step = findStep( sequence );
	
	// perform a binary search for missing element in O(log(n))
	
	int start = 0;
	int end = sequence.size() - 1;
	boolean foundMissing = false;
	int missing = -1;
	
	while ( start <= end ) {
		
		int middle = start + ( end - start ) / 2;
		
		int expected = sequence.get( 0 ) + step * middle;
		
		if ( expected == sequence.get( middle ) ) {
			start = middle + 1;
		} else {
			end = middle - 1;
			// found a candidate for missing element, however must continue
			// binary search all the way to make sure it is the right one
			foundMissing = true;
			missing = expected;
		}
	}
	
	if ( foundMissing ) {
		return missing;
	} else {
		// all elements in sequence were valid, assume missing must be at end of sequence
		return sequence.get( 0 ) + step * sequence.size();	
	}
}

public static int findStep( List<Integer> sequence ) {
	int first = sequence.get( 0 );
	int second = sequence.get( 1 );
	int third = sequence.get( 2 );
	
	int step = Math.min( Math.abs( second - first ), Math.abs( third - second ) );
	
	if ( second - first < 0 ) {
		step *= -1;
	}
	
	return step;
}

For sequence, the formula is 0.5 * (first + last) * (size + 1), minus the real summation should be missing number.

def missingNumberByFormula(nums):
    total = sum(nums)
    n = nums.__len__()
    return int(0.5 * (nums[0] + nums[n - 1]) * (n + 1) - total)

def missingNumberByFormula(nums):
    total = sum(nums)
    n = nums.__len__()
    return int(0.5 * (nums[0] + nums[n - 1]) * (n + 1) - total)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
*
*/

/**
* @author abhishek
*
*/
public class MissingEleInAP {
static List<Integer> l = new ArrayList<Integer>();
/**
* @param args
*/
public static void main(String[] args) {

l.add(-2);
l.add(-8);
l.add(-11);
l.add(-14);
l.add(20);

int d = getDifference(l);
int size = l.size();
for(int i=1; i<size;i++){
if(l.get(i) != l.get(0)+(i+1-1)*d){
l.add(i,l.get(0)+(i+1-1)*d);
size = l.size();
}
}
System.out.println(l);
}

public static int getDifference(List<Integer> l){
return (l.get(1)-l.get(0) == l.get(2)-l.get(1)) ? l.get(1)-l.get(0) : (l.get(2)-l.get(1) == l.get(3)-l.get(2)) ? l.get(2)-l.get(1) : l.get(1)-l.get(0);
}
}

sorry, what is A.P.?

public class MissingAP {
public static void main(String args[]) {

int arr[] = { 10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
int difference[] = new int[arr.length - 1];
int missingTerm;

for (int i = 1; i < arr.length; i++) {
difference[i - 1] = arr[i] - arr[i - 1];
}
for (int j = 0; j < arr.length - 1; j++) {

if (difference[j] != difference[j + 1]) {
missingTerm = arr[j] + difference[j + 1];
System.out.println("The missing term is: " + missingTerm);

break;

}
}
}
}

int findMissingAP(std::vector<int>& series)
{
//Assuming there is only one missing from AP
//Assuming there are at least 4 elements in series
//Assuming missing element is not zero
int size = series.size();
if( size < 4)
{
std::cout<<" There are not enough elements in series"<<"\n";
}

int diff1 = 0;
int diff2 = 0;
int diff3 = 0;

if( size >= 4)
{
int first = series.at(0);
int second = series.at(1);
int third = series.at(2);
int fourth = series.at(3);

diff1 = second - first;
diff2 = third - second;
diff3 = fourth - third;
}

int diff=0;
if( diff1 == diff2 )
{
diff = diff1;
}
else if( diff1 == diff3)
{
diff= diff1;
}
else if(diff2 == diff3)
{
diff = diff2;
}

auto end = series.end();
int result=0;
for( auto it = series.begin(); it != end; )
{
int x = *it;
int y = *(++it);
if( y - x == diff)
continue;
result = x + diff ;
break;
}
return result;
}

int findMissingAP(std::vector<int>& series)
{
    //Assuming there is only one missing from AP
    //Assuming there are at least 4 elements in series
    //Assuming missing element is not zero
    int size = series.size();
    if( size < 4)
    {
        std::cout<<" There are not enough elements in series"<<"\n";
    }
    
    int diff1 = 0;
    int diff2 = 0;
    int diff3 = 0;
    
    if( size >= 4)
    {
       int first  = series.at(0);
       int second = series.at(1);
       int third  = series.at(2);
       int fourth = series.at(3);
    
       diff1 = second - first;
       diff2 = third - second;
       diff3 = fourth - third;
    }
    
    int diff=0;
    if( diff1 == diff2 )
    {
        diff = diff1;
    }
    else if( diff1 == diff3)
    {
        diff= diff1;
    }
    else if(diff2 == diff3)
    {
        diff = diff2;
    }
    
    auto end = series.end();
    int result=0;
    for( auto it = series.begin(); it != end; )
    {
        int x = *it;      
        int y = *(++it);
        if( y - x == diff)
           continue;
        result = x + diff ;
         break;       
    }
    return result;

}

int findMissingAP(const std::vector<int>& series)
{
    //Assuming there is only one missing from AP
    //Assuming there are at least 4 elements in series
    //Assuming missing element is not zero
    int size = series.size();
    if( size < 4)
    {
        std::cout<<" There are not enough elements in series"<<"\n";
    }
    
    int diff1 = 0;
    int diff2 = 0;
    int diff3 = 0;
    
    if( size >= 4)
    {
       int first  = series.at(0);
       int second = series.at(1);
       int third  = series.at(2);
       int fourth = series.at(3);
    
       diff1 = second - first;
       diff2 = third - second;
       diff3 = fourth - third;
    }
    
    int diff=0;
    if( diff1 == diff2 )
    {
        diff = diff1;
    }
    else if( diff1 == diff3)
    {
        diff= diff1;
    }
    else if(diff2 == diff3)
    {
        diff = diff2;
    }
    
    auto end = series.end();
    int result=0;
    for( auto it = series.begin(); it != end; )
    {
        int x = *it;      
        int y = *(++it);
        if( y - x == diff)
           continue;
        result = x + diff ;
         break;       
    }
    return result;
 }

this can be solved with binary search.
let's find the d = Math.min(a[1] - a[0], a[2] - a[1]); we should ask how we should handle the case when number of elements less than 3.

now we do binary search comparing whether element at position i equal or not to a[0] + i * d, if it's not the answer in left side, otherwise in right side

Sum of AP with n elements is - n/2 (a + d(n-1)). Subtract the sum of given elements form this number that will be missing element. Space complexity O(1) , run time complexity O(n)

Sum of elements in AP is n/2(a + d(n-1)). Subtract the sum of given numbers from this and you will get the missing number.
Space complexity - O(1)
Time complexity - O(n)

In case of one missing number, the sum approach will solve the problem.
If there are multiple missings in different locations, then we can solve it in time O(2*n) and space O(1):
- run one iteration to find the minimum difference between the numbers. the min would be 'd'.
- run the second iteration, and detect the missing numbers between each two items in the array. E.g., if a[i]-a[i-1] == d*3, then it means there are 2 numbers missing between i and i-1.

import java.util.Scanner;
public class DemoClass {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int i,d,num,n;
n = input.nextInt();
int[] a = new int[n];
for(i=0; i<n; i++){
a[i] = input.nextInt();
}
d=a[1]-a[0];
for(i=0; i<n; i++){
if((a[i+1]-a[i])!=d){
num=a[i]+d;
System.out.println("Missing number is "+num+" and its position should be "+(i+1));
}
}
}
}

import java.util.Scanner;
public class DemoClass {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int i,d,num,n;
		n = input.nextInt();
		int[] a = new int[n];
		for(i=0; i<n; i++){
			a[i] = input.nextInt();
		}
		d=a[1]-a[0]; 
		for(i=0; i<n; i++){
			if((a[i+1]-a[i])!=d){
				num=a[i]+d;
				System.out.println("Missing number is "+num+" and its position should be "+(i+1));
			}
		}
	}
}

/*I am assuming that the number which the user will insert are ordered in AP. And I am also taking input of 'd' from user*/ 
import java.util.*;
public class DemoClass {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int i,d,num,n;
		n = input.nextInt();
		d = input.nextInt();
		int[] a = new int[n];
		for(i=0; i<n; i++){
			a[i] = input.nextInt();
		} 
		for(i=0; i<n; i++){
			if((a[i+1]-a[i])!=d){
				num=a[i]+d;
				System.out.println("Missing number is "+num+" and its position should be "+(i+1));
			}
		}
	}
}

/*I am assuming that the number which the user will insert are ordered in AP. And I am also taking input of 'd' from user*/ 
import java.util.*;
public class DemoClass {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int i,d,num,n;
		n = input.nextInt();
		d = input.nextInt();
		int[] a = new int[n];
		for(i=0; i<n; i++){
			a[i] = input.nextInt();
		} 
		for(i=0; i<n; i++){
			if((a[i+1]-a[i])!=d){
				num=a[i]+d;
				System.out.println("Missing number is "+num+" and its position should be "+(i+1));
			}
		}
	}
}

Java Codes

/**
     * This function finds how many and where the elements are missing in an arithmetic progression.
     * Its time complexity is O(n) and space complexity is O(1).
     *
     * If missing elements need to be specified, an additional array buffer is necessary for the task which makes
     * the space complexity O(n).
     */
    double[] locateMissingElements(double[] ap) {
        if (ap == null) {
            return null;
        }

        if (ap.length < 3) {
            return ap;
        }

        double commonDiff = ap[ap.length - 1];
        for (int i = 0; i < ap.length - 1; i++) {
            ap[i] = ap[i + 1] - ap[i];
            if (Math.abs(ap[i]) < Math.abs(commonDiff)) {
                commonDiff = ap[i];
            }
        }
        ap[ap.length - 1] = 0;

        // if the common diff is 0, technically no elements are actually missing. Just make this an exception case.
        if (commonDiff == 0) {
            return null;
        }

        // how many elements are missing between index n and n+1
        for (int i = 0; i < ap.length; i++) {
            ap[i] = ap[i] / commonDiff - 1;
        }

        return ap;
    }

using System;

class Solution
{
    static void Main(string[] args)
    {
        //int[] sequence = new int[] { 10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        //int[] sequence = new int[] { -10, -8, -4, -2, 0, 2, 4, 6, 8, 10, 12 };
        //int[] sequence = new int[] { 10, 8, 6, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        //int[] sequence = new int[] { 10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        
        int? missingTerm = FindMissingArithmeticSequenceTerm(sequence);
        
        if (missingTerm.HasValue)
        {
            Console.Out.WriteLine(missingTerm.Value);
        }
        else
        {
            Console.Out.WriteLine("No missing terms");
        }
    }
    
    public static int? FindMissingArithmeticSequenceTerm(int[] sequence)
    {
        if (sequence.Length < 4)
        {
            throw new Exception("Sequence can not be determined with less than 4 terms");
        }
        
        int stepOne = sequence[1] - sequence[0];
        int stepTwo = sequence[2] - sequence[1];
        int step = stepOne == stepTwo ? stepOne : sequence[3] - sequence[2];
        
        for (int i = 1; i < sequence.Length; i++)
        {
            if ((sequence[i] - sequence[i - 1]) != step)
            {
                return sequence[i - 1] + step;
            }
        }
        
        return null;
    }
}

using System;

class Solution
{
    static void Main(string[] args)
    {
        //int[] sequence = new int[] { 10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        //int[] sequence = new int[] { -10, -8, -4, -2, 0, 2, 4, 6, 8, 10, 12 };
        //int[] sequence = new int[] { 10, 8, 6, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        //int[] sequence = new int[] { 10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12 };
        
        int? missingTerm = FindMissingArithmeticSequenceTerm(sequence);
        
        if (missingTerm.HasValue)
        {
            Console.Out.WriteLine(missingTerm.Value);
        }
        else
        {
            Console.Out.WriteLine("No missing terms");
        }
    }
    
    public static int? FindMissingArithmeticSequenceTerm(int[] sequence)
    {
        if (sequence.Length < 4)
        {
            throw new Exception("Sequence can not be determined with less than 4 terms");
        }
        
        int stepOne = sequence[1] - sequence[0];
        int stepTwo = sequence[2] - sequence[1];
        int step = stepOne == stepTwo ? stepOne : sequence[3] - sequence[2];
        
        for (int i = 1; i < sequence.Length; i++)
        {
            if ((sequence[i] - sequence[i - 1]) != step)
            {
                return sequence[i - 1] + step;
            }
        }
        
        return null;
    }
}

java

    public static List<Integer> findMissingElements(int[] arr) {
        List<Integer> missingElements = new ArrayList<>();
        if (arr == null || arr.length < 3) {
            return missingElements;
        }

        int diff = Math.min(Math.abs(arr[1] - arr[0]), Math.abs(arr[2] - arr[1]));
        if (arr[1] - arr[0] < 0) {
            diff = -diff;
        }

        for (int i = 1; i < arr.length; i = i+2) {
            int prevDiff = arr[i] - arr[i-1];
            int nextDiff = diff;
            // check if the end of array
            if (i+1 < arr.length) {
                nextDiff = arr[i+1] - arr[i];
            }
            if (prevDiff != diff) {
                int missingElement = arr[i-1] + diff;
                while (missingElement != arr[i]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
            if (nextDiff != diff) {
                int missingElement = arr[i] + diff;
                while (missingElement != arr[i+1]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
        }

        return missingElements;
    }

import java.util.ArrayList;
import java.util.List;

public class MissingElementsInAP {

    public static void main(String[] args) {
        int[] arr1 = {10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12, -14};
        int[] arr2 = {-14, -12, -10, -6, -4, -2, 0, 2, 4, 6, 8, 10, 14};
        int[] arr3 = {0, 2, 4, 6, 8, 10, 14, 18};
        int[] arr4 = {-15, -3, 0, 3, 6, 9, 15};
        int[] arr5 = {12, 4, 2};
        int[] arr6 = {12, 4};

        System.out.println("MissingElements is 6 ? " + findMissingElements(arr1));
        System.out.println("MissingElements is -8, 12 ? " + findMissingElements(arr2));
        System.out.println("MissingElements is 12, 16 ? " + findMissingElements(arr3));
        System.out.println("MissingElements is -12, -9, -6, 12 ? " + findMissingElements(arr4));
        System.out.println("MissingElements is 10, 8, 6 ? " + findMissingElements(arr5));
        System.out.println("MissingElements not found ? " + findMissingElements(arr6));
    }

    public static List<Integer> findMissingElements(int[] arr) {
        List<Integer> missingElements = new ArrayList<>();
        if (arr == null || arr.length < 3) {
            return missingElements;
        }

        int diff = Math.min(Math.abs(arr[1] - arr[0]), Math.abs(arr[2] - arr[1]));
        if (arr[1] - arr[0] < 0) {
            diff = -diff;
        }

        for (int i = 1; i < arr.length; i = i+2) {
            int prevDiff = arr[i] - arr[i-1];
            int nextDiff = diff;
            // check if the end of array
            if (i+1 < arr.length) {
                nextDiff = arr[i+1] - arr[i];
            }
            if (prevDiff != diff) {
                int missingElement = arr[i-1] + diff;
                while (missingElement != arr[i]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
            if (nextDiff != diff) {
                int missingElement = arr[i] + diff;
                while (missingElement != arr[i+1]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
        }

        return missingElements;
    }

}

public static void main(String[] args) {
int a[] = {-10,-8,-6,-4,-2,0,2,4,8};
int diff=0;
int missingElement=0;
if(Math.abs(a[0]-a[1]) == Math.abs(a[1]-a[2])){
diff = Math.abs(a[0]-a[1]);
}
else if(Math.abs(a[1]-a[2]) == Math.abs(a[2]-a[3])){
diff = Math.abs(a[1]-a[2]);
}
else if(Math.abs(a[0]-a[1]) == Math.abs(a[2]-a[3])){
diff = Math.abs(a[0]-a[1]);
}
for(int i=0;i<a.length-1;i++){
if(Math.abs(a[i+1]-a[i]) != diff){
missingElement = a[i]+diff;
break;
}
}
System.out.println(missingElement);

}

possible c# implementation.
O(logn).

using System;

namespace MissingElementAPSequence {

    public class MissingElementApSequence {
        
        static int? Find( int[] apArr ){

            int step = GetStep( apArr, 0 );

            if( step == 0 ) { return GetRes( apArr, 0 ); }

            int begin = 0;
            int end = apArr.Length - 1;

            while ( end - begin != 1 ) {

                if ( end - begin < 4 ) {
                    var res = GetRes( apArr, begin );
                    if( res != 0 ) { return  res; }
                }

                int mid = ( end + begin ) / 2;
                int expected = apArr[ 0 ] + mid * step;

                if ( expected != apArr[ mid ] ) { end = mid; }
                else { begin = mid; }
            }
            return null; // A.P. does not have missing elements
        }

        static int[] _get( int[] arr, int beg ) {

            int oneMinusZero = arr[ beg + 1 ] - arr[ beg ];
            int twoMinusOne = arr[ beg + 2 ] - arr[ beg + 1 ];

            if ( oneMinusZero == twoMinusOne ){
                return new [] { oneMinusZero, 0 };
            }
            if ( Math.Abs( oneMinusZero ) > Math.Abs( twoMinusOne ) ) {
                return new [] { 0, arr[ beg ] + twoMinusOne };
            }
            return new [] { 0, arr[ beg + 1 ] + oneMinusZero };
        }

        static int GetRes( int[] arr, int beg ){
            return _get( arr, beg )[ 1 ];
        }

        static int GetStep( int[] arr, int beg ) {
            return _get( arr, beg )[ 0 ];
        }

        public static void Main() {
            //int[] arr = { 10, 8,/*6,*/4, 2, 0, -2, -4, -6, -8, -10, -12, -14, -16, -18, -20, -22, -24, -26, -28, -30, };
            int[] arr = { -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28,/* 30,*/ 32, 34, 36 };
            var res = Find(arr);
            Console.WriteLine( res );
        }
    }    
}

import java.util.Scanner;


public class missingAP {

public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of elements");
int n= scan.nextInt();
int []arr= new int[n];
System.out.println("Enter the elements");
for(int i=0;i<arr.length;i++)
{
arr[i]= scan.nextInt();
}
System.out.println("Checked!");
int a=arr[0];
int d=arr[1]-arr[0];
int missingValue=0;
for(int i=1;i<arr.length;i++)
{
missingValue=(a+(i)*d);
if(arr[i]!=missingValue)

{
System.out.println("The missing value is" +missingValue);
break;
}

}
if(missingValue==arr[arr.length-1])
System.out.println("All values are present!");
}
}

import java.util.Scanner;


public class missingAP {

public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of elements");
int n= scan.nextInt();
int []arr= new int[n];
System.out.println("Enter the elements");
for(int i=0;i<arr.length;i++)
{
arr[i]= scan.nextInt();
}
System.out.println("Checked!");
int a=arr[0];
int d=arr[1]-arr[0];
int missingValue=0;
for(int i=1;i<arr.length;i++)
{
missingValue=(a+(i)*d);
if(arr[i]!=missingValue)

{
System.out.println("The missing value is" +missingValue);
break;
}

}
if(missingValue==arr[arr.length-1])
System.out.println("All values are present!");
}
}

import java.util.Scanner;


public class missingAP {

public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of elements");
int n= scan.nextInt();
int []arr= new int[n];
System.out.println("Enter the elements");
for(int i=0;i<arr.length;i++)
{
arr[i]= scan.nextInt();
}
System.out.println("Checked!");
int a=arr[0];
int d=arr[1]-arr[0];
int missingValue=0;
for(int i=1;i<arr.length;i++)
{
missingValue=(a+(i)*d);
if(arr[i]!=missingValue)

{
System.out.println("The missing value is" +missingValue);
break;
}

}
if(missingValue==arr[arr.length-1])
System.out.println("All values are present!");
}
}

public class ArithmaticProgression {
	public static void main(String[] args) {
		System.out.print("Enter Array size: ");
		Scanner scanner = new Scanner(System.in);
		int size = scanner.nextInt();
		int array[] = new int[size];
		int total = 0;
		for (int i =0; i<size; i++) {
			System.out.print("Enter " + (i+1) + " element: ");
			array[i] = scanner.nextInt();
			total = total + array[i];
		}
		
		/*
		 * Sum of arithmatic expression is n * (A0 + An) / 2. In below equation
		 * I am taking size + 1 because it missed one element and added next
		 * element.
		 */
		int totalByEquation = (size + 1) * (array[0] + array[size - 1])/2;
		
		System.out.println("Missing element is: " + (totalByEquation - total));
	}
}

Output:
Enter Array size: 5
Enter 1 element: 2
Enter 2 element: 5
Enter 3 element: 11
Enter 4 element: 14
Enter 5 element: 17
Missing element is: 8

public class ArithmaticProgression {
	public static void main(String[] args) {
		System.out.print("Enter Array size: ");
		Scanner scanner = new Scanner(System.in);
		int size = scanner.nextInt();
		int array[] = new int[size];
		int total = 0;
		for (int i =0; i<size; i++) {
			System.out.print("Enter " + (i+1) + " element: ");
			array[i] = scanner.nextInt();
			total = total + array[i];
		}
		
		/*
		 * Sum of arithmatic expression is n * (A0 + An) / 2. In below equation
		 * I am taking size + 1 because it missed one element and added next
		 * element.
		 */
		int totalByEquation = (size + 1) * (array[0] + array[size - 1])/2;
		
		System.out.println("Missing element is: " + (totalByEquation - total));
	}
}

Output:
Enter Array size: 5
Enter 1 element: 2
Enter 2 element: 5
Enter 3 element: 11
Enter 4 element: 14
Enter 5 element: 17
Missing element is: 8

public class ArithmaticProgression {
	public static void main(String[] args) {
		System.out.print("Enter Array size: ");
		Scanner scanner = new Scanner(System.in);
		int size = scanner.nextInt();
		int array[] = new int[size];
		int total = 0;
		for (int i =0; i<size; i++) {
			System.out.print("Enter " + (i+1) + " element: ");
			array[i] = scanner.nextInt();
			total = total + array[i];
		}
		
		/*
		 * Sum of arithmatic expression is n * (A0 + An) / 2. In below equation
		 * I am taking size + 1 because it missed one element and added next
		 * element.
		 */
		int totalByEquation = (size + 1) * (array[0] + array[size - 1])/2;
		
		System.out.println("Missing element is: " + (totalByEquation - total));
	}
}

Output:

Enter Array size: 5
Enter 1 element: 2
Enter 2 element: 5
Enter 3 element: 11
Enter 4 element: 14
Enter 5 element: 17
Missing element is: 8

first & last element of given sequence are always part of it. perform 3 subtractions: 1-2, 2-3 & 3-4 and the majority is your difference. Finally Start traversing from beginning checking difference against the computed one. O(n)

def missingNumberByFormula(nums):
    total = sum(nums)
    n = nums.__len__()
    return int(0.5 * (nums[0] + nums[n - 1]) * (n + 1) - total)

/*I am assuming that the number which the user will insert are ordered in AP. And I am also taking input of 'd' from user*/ 
import java.util.*;
public class DemoClass {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int i,d,num,n;
		n = input.nextInt();
		d = input.nextInt();
		int[] a = new int[n];
		for(i=0; i<n; i++){
			a[i] = input.nextInt();
		} 
		for(i=0; i<n; i++){
			if((a[i+1]-a[i])!=d){
				num=a[i]+d;
				System.out.println("Missing number is "+num+" and its position should be "+(i+1));
			}
		}
	}
}

/*I am assuming that the number which the user will insert are ordered in AP. And I am also taking input of 'd' from user*/ 
import java.util.*;
public class DemoClass {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int i,d,num,n;
		n = input.nextInt();
		d = input.nextInt();
		int[] a = new int[n];
		for(i=0; i<n; i++){
			a[i] = input.nextInt();
		} 
		for(i=0; i<n; i++){
			if((a[i+1]-a[i])!=d){
				num=a[i]+d;
				System.out.println("Missing number is "+num+" and its position should be "+(i+1));
			}
		}
	}
}

import java.util.ArrayList;
import java.util.List;

public class MissingElementsInAP {

    public static void main(String[] args) {
        int[] arr1 = {10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12, -14};
        int[] arr2 = {-14, -12, -10, -6, -4, -2, 0, 2, 4, 6, 8, 10, 14};
        int[] arr3 = {0, 2, 4, 6, 8, 10, 14, 18};
        int[] arr4 = {-15, -3, 0, 3, 6, 9, 15};
        int[] arr5 = {12, 4, 2};
        int[] arr6 = {12, 4};

        System.out.println("MissingElements is 6 ? " + findMissingElements(arr1));
        System.out.println("MissingElements is -8, 12 ? " + findMissingElements(arr2));
        System.out.println("MissingElements is 12, 16 ? " + findMissingElements(arr3));
        System.out.println("MissingElements is -12, -9, -6, 12 ? " + findMissingElements(arr4));
        System.out.println("MissingElements is 10, 8, 6 ? " + findMissingElements(arr5));
        System.out.println("MissingElements not found ? " + findMissingElements(arr6));
    }

    public static List<Integer> findMissingElements(int[] arr) {
        List<Integer> missingElements = new ArrayList<>();
        if (arr == null || arr.length < 3) {
            return missingElements;
        }

        int diff = Math.min(Math.abs(arr[1] - arr[0]), Math.abs(arr[2] - arr[1]));
        if (arr[1] - arr[0] < 0) {
            diff = -diff;
        }

        for (int i = 1; i < arr.length; i = i+2) {
            int prevDiff = arr[i] - arr[i-1];
            int nextDiff = diff;
            // check if the end of array
            if (i+1 < arr.length) {
                nextDiff = arr[i+1] - arr[i];
            }
            if (prevDiff != diff) {
                int missingElement = arr[i-1] + diff;
                while (missingElement != arr[i]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
            if (nextDiff != diff) {
                int missingElement = arr[i] + diff;
                while (missingElement != arr[i+1]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
        }

        return missingElements;
    }

}

import java.util.ArrayList;
import java.util.List;

public class MissingElementsInAP {

    public static void main(String[] args) {
        int[] arr1 = {10, 8, 4, 2, 0, -2, -4, -6, -8, -10, -12, -14};
        int[] arr2 = {-14, -12, -10, -6, -4, -2, 0, 2, 4, 6, 8, 10, 14};
        int[] arr3 = {0, 2, 4, 6, 8, 10, 14, 18};
        int[] arr4 = {-15, -3, 0, 3, 6, 9, 15};
        int[] arr5 = {12, 4, 2};
        int[] arr6 = {12, 4};

        System.out.println("MissingElements is 6 ? " + findMissingElements(arr1));
        System.out.println("MissingElements is -8, 12 ? " + findMissingElements(arr2));
        System.out.println("MissingElements is 12, 16 ? " + findMissingElements(arr3));
        System.out.println("MissingElements is -12, -9, -6, 12 ? " + findMissingElements(arr4));
        System.out.println("MissingElements is 10, 8, 6 ? " + findMissingElements(arr5));
        System.out.println("MissingElements not found ? " + findMissingElements(arr6));
    }

    public static List<Integer> findMissingElements(int[] arr) {
        List<Integer> missingElements = new ArrayList<>();
        if (arr == null || arr.length < 3) {
            return missingElements;
        }

        int diff = Math.min(Math.abs(arr[1] - arr[0]), Math.abs(arr[2] - arr[1]));
        if (arr[1] - arr[0] < 0) {
            diff = -diff;
        }

        for (int i = 1; i < arr.length; i = i+2) {
            int prevDiff = arr[i] - arr[i-1];
            int nextDiff = diff;
            // check if the end of array
            if (i+1 < arr.length) {
                nextDiff = arr[i+1] - arr[i];
            }
            if (prevDiff != diff) {
                int missingElement = arr[i-1] + diff;
                while (missingElement != arr[i]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
            if (nextDiff != diff) {
                int missingElement = arr[i] + diff;
                while (missingElement != arr[i+1]) {
                    missingElements.add(missingElement);
                    missingElement += diff;
                }
            }
        }

        return missingElements;
    }

}

solution with O(n) time and O(1) space complexity.. let me know if m not correct..

public class ArithmaticProg {

	public static void main(String[] args){
		int[] a={2,5,8,14};
		ArithmaticProg ap = new ArithmaticProg();
		System.out.println("--"+ap.getMissingElement(a));
	}
	public int getMissingElement(int[] a){
		int missingElement=0,compare;
		
		for (int i=1 ;i<a.length-1 ;i++){
			compare = Integer.compare((a[i]-a[i-1]),(a[i+1]-a[i]));
			if(compare!=0){
				if(compare==1)
					missingElement=(a[i]+a[i-1])/2;
				else
					missingElement=(a[i+1]+a[i])/2;
				return missingElement;
			}
		}
		return missingElement;
	}
}