CareerCup

1) Find the min and max.
2) Calculate expected d for the A.P, max = min + (n - 1) * d
3) Take the XOR from min to max with expected d (expected series)
4) Take the XOR with all the elements in array.
If 0, the series else not

If the array elements are unsorted, then it would seem that the logic of checking the difference between adjacent elements does not work. With sorting, we can have two solutions.
+ nlogn sort + check the difference between adjacent elements
+ O(n) sort....counting sort + check the difference between adjacent elements
Ofcourse if the array contains negative elements, then counting sort is tricky....

Let me think some more...

Whats wrong in below soln:
Step1: Get min(first element) and Max(last element)
Step2: Get difference d by formula An(Max element) = A1(Min element) + (n-1)d
Step3: For loop: check if Ai+d exist in given Array.
For example: Given Array: {7,5,1,3}
Step1: min:1, max=7
Step2: d= (7-1)/3 = 2
Step3: for loop: check if 1+2=3 exist in an array-> yes, so next element 3+2->5 n so on

int main()
{
	int a[] = { 1,2,4,5,6,7 };
	int l = 7;
	int arith_seq = a[1] - a[0];
	int is_seq = 1;
	int ctr = 1;
	while (ctr < l)
	{
		//printf("\n ctr = %d arith_seq = %d a[ctr - 1] = %d a[ctr] = %d", ctr,arith_seq,a[ctr-1],a[ctr]);
		if (a[ctr] - a[ctr-1] != arith_seq)
		{
			is_seq = 0;
			break;
		}
		ctr++;

	}
	if (is_seq) printf("Seq");
	else printf("Not seq");
	scanf_s("%d", &l);

}

/*** Include Header file for basic I/O ***/
#include<stdio.h>
/*** Include Header file for console I/O ***/
#include<conio.h>

#define SIZE	10

/*** main function definition: Begin ***/
int main()
{
    /* Variable definition */
	int iArray1[SIZE] = {0, 5, 10, 15, 20, 25, 30, 35, 40, 45};
	int iArray2[SIZE] = {1, 3, 5, 7, 10, 11, 13, 15, 17, 19};
	int iArray3[SIZE] = {10, 12, 16, 22, 14, 20, 24, 18, 28, 26};
	int iArray4[SIZE] = {45, 40, 35, 30, 25, 20, 15, 10, 5, 0};
	
	/* Function Prototype */
	int CheckArray (const int iArray[]);
	
	/* Function call to clear off the user screen */
    //clrscr();

	/* Check if iArray1 is arithmetic sequence */
	if (CheckArray (iArray1))
		printf("\niArray1 is arithmetic sequence.");
	else
		printf("\niArray1 is not arithmetic sequence.");

	/* Check if iArray2 is arithmetic sequence */
	if (CheckArray (iArray2))
		printf("\niArray2 is arithmetic sequence.");
	else
		printf("\niArray2 is not arithmetic sequence.");

	/* Check if iArray3 is arithmetic sequence */
	if (CheckArray (iArray3))
		printf("\niArray3 is arithmetic sequence.");
	else
		printf("\niArray3 is not arithmetic sequence.");

	/* Check if iArray4 is arithmetic sequence */
	if (CheckArray (iArray4))
		printf("\niArray4 is arithmetic sequence.");
	else
		printf("\niArray4 is not arithmetic sequence.");		

	/* Get a character from the input device */
    getch();
}
/*** main function definition: End ***/

/*** CheckArray function definition: Begin ***/
int CheckArray (const int iArray[])
{
	/* Variable definition */
	int ii, iDistance;
	
	/* Find the distance between first two elements of the array */
	iDistance = iArray[1] - iArray[0];
		
	/* Check for the arithmetic sequence */
	for (ii = 1; ii < SIZE-1; ++ii)
	{
		if ((iArray[ii+1] - iArray[ii]) % iDistance != 0)
			return 0;
	}
	
	return 1;
}
/*** CheckArray function definition: End ***/

/*** Include Header file for basic I/O ***/
#include<stdio.h>
/*** Include Header file for console I/O ***/
#include<conio.h>

#define SIZE	10

/*** main function definition: Begin ***/
int main()
{
    /* Variable definition */
	int iArray1[SIZE] = {0, 5, 10, 15, 20, 25, 30, 35, 40, 45};
	int iArray2[SIZE] = {1, 3, 5, 7, 10, 11, 13, 15, 17, 19};
	int iArray3[SIZE] = {10, 12, 16, 22, 14, 20, 24, 18, 28, 26};
	int iArray4[SIZE] = {45, 40, 35, 30, 25, 20, 15, 10, 5, 0};
	
	/* Function Prototype */
	int CheckArray (const int iArray[]);
	
	/* Function call to clear off the user screen */
    //clrscr();

	/* Check if iArray1 is arithmetic sequence */
	if (CheckArray (iArray1))
		printf("\niArray1 is arithmetic sequence.");
	else
		printf("\niArray1 is not arithmetic sequence.");

	/* Check if iArray2 is arithmetic sequence */
	if (CheckArray (iArray2))
		printf("\niArray2 is arithmetic sequence.");
	else
		printf("\niArray2 is not arithmetic sequence.");

	/* Check if iArray3 is arithmetic sequence */
	if (CheckArray (iArray3))
		printf("\niArray3 is arithmetic sequence.");
	else
		printf("\niArray3 is not arithmetic sequence.");

	/* Check if iArray4 is arithmetic sequence */
	if (CheckArray (iArray4))
		printf("\niArray4 is arithmetic sequence.");
	else
		printf("\niArray4 is not arithmetic sequence.");		

	/* Get a character from the input device */
    getch();
}
/*** main function definition: End ***/

/*** CheckArray function definition: Begin ***/
int CheckArray (const int iArray[])
{
	/* Variable definition */
	int ii, iDistance;
	
	/* Find the distance between first two elements of the array */
	iDistance = iArray[1] - iArray[0];
		
	/* Check for the arithmetic sequence */
	for (ii = 1; ii < SIZE-1; ++ii)
	{
		if ((iArray[ii+1] - iArray[ii]) % iDistance != 0)
			return 0;
	}
	
	return 1;
}
/*** CheckArray function definition: End ***/

/*** Include Header file for basic I/O ***/
#include<stdio.h>
/*** Include Header file for console I/O ***/
#include<conio.h>

#define SIZE	10

/*** main function definition: Begin ***/
int main()
{
    /* Variable definition */
	int iArray1[SIZE] = {0, 5, 10, 15, 20, 25, 30, 35, 40, 45};
	int iArray2[SIZE] = {1, 3, 5, 7, 10, 11, 13, 15, 17, 19};
	int iArray3[SIZE] = {10, 12, 16, 22, 14, 20, 24, 18, 28, 26};
	int iArray4[SIZE] = {45, 40, 35, 30, 25, 20, 15, 10, 5, 0};
	
	/* Function Prototype */
	int CheckArray (const int iArray[]);
	
	/* Function call to clear off the user screen */
    //clrscr();

	/* Check if iArray1 is arithmetic sequence */
	if (CheckArray (iArray1))
		printf("\niArray1 is arithmetic sequence.");
	else
		printf("\niArray1 is not arithmetic sequence.");

	/* Check if iArray2 is arithmetic sequence */
	if (CheckArray (iArray2))
		printf("\niArray2 is arithmetic sequence.");
	else
		printf("\niArray2 is not arithmetic sequence.");

	/* Check if iArray3 is arithmetic sequence */
	if (CheckArray (iArray3))
		printf("\niArray3 is arithmetic sequence.");
	else
		printf("\niArray3 is not arithmetic sequence.");

	/* Check if iArray4 is arithmetic sequence */
	if (CheckArray (iArray4))
		printf("\niArray4 is arithmetic sequence.");
	else
		printf("\niArray4 is not arithmetic sequence.");		

	/* Get a character from the input device */
    getch();
}
/*** main function definition: End ***/

/*** CheckArray function definition: Begin ***/
int CheckArray (const int iArray[])
{
	/* Variable definition */
	int ii, iDistance;
	
	/* If the number is elements is 1 or 2 it is always an arithmetic sequence */
	if (SIZE < 3)
		return 1;
		
	/* Find the distance between first two elements of the array */
	iDistance = iArray[1] - iArray[0];
		
	/* Check for the arithmetic sequence */
	for (ii = 1; ii < SIZE-1; ++ii)
	{
		if ((iArray[ii+1] - iArray[ii]) % iDistance != 0)
			return 0;
	}
	
	return 1;
}
/*** CheckArray function definition: End ***/

/*** Include Header file for basic I/O ***/
#include<stdio.h>
/*** Include Header file for console I/O ***/
#include<conio.h>

#define SIZE	10

/*** main function definition: Begin ***/
int main()
{
    /* Variable definition */
	int iArray1[SIZE] = {0, 5, 10, 15, 20, 25, 30, 35, 40, 45};
	int iArray2[SIZE] = {1, 3, 5, 7, 10, 11, 13, 15, 17, 19};
	int iArray3[SIZE] = {10, 12, 16, 22, 14, 20, 24, 18, 28, 26};
	int iArray4[SIZE] = {45, 40, 35, 30, 25, 20, 15, 10, 5, 0};
	
	/* Function Prototype */
	int CheckArray (const int iArray[]);
	
	/* Function call to clear off the user screen */
    //clrscr();

	/* Check if iArray1 is arithmetic sequence */
	if (CheckArray (iArray1))
		printf("\niArray1 is arithmetic sequence.");
	else
		printf("\niArray1 is not arithmetic sequence.");

	/* Check if iArray2 is arithmetic sequence */
	if (CheckArray (iArray2))
		printf("\niArray2 is arithmetic sequence.");
	else
		printf("\niArray2 is not arithmetic sequence.");

	/* Check if iArray3 is arithmetic sequence */
	if (CheckArray (iArray3))
		printf("\niArray3 is arithmetic sequence.");
	else
		printf("\niArray3 is not arithmetic sequence.");

	/* Check if iArray4 is arithmetic sequence */
	if (CheckArray (iArray4))
		printf("\niArray4 is arithmetic sequence.");
	else
		printf("\niArray4 is not arithmetic sequence.");		

	/* Get a character from the input device */
    getch();
}
/*** main function definition: End ***/

/*** CheckArray function definition: Begin ***/
int CheckArray (const int iArray[])
{
	/* Variable definition */
	int ii, iDistance;
	
	/* If the number is elements is 1 or 2 it is always an arithmetic sequence */
	if (SIZE < 3)
		return 1;
		
	/* Find the distance between first two elements of the array */
	iDistance = iArray[1] - iArray[0];
		
	/* Check for the arithmetic sequence */
	for (ii = 1; ii < SIZE-1; ++ii)
	{
		if ((iArray[ii+1] - iArray[ii]) % iDistance != 0)
			return 0;
	}
	
	return 1;
}
/*** CheckArray function definition: End ***/

public boolean checkArithmeticSequence(int[] array) {
		if(array == null || array.length == 0) return false;	//not a sequence at all
		if(array.length == 1) return true;	//may be considered a sequence, but I would talk to the interviewer
		int firstWhenOrdered = Integer.MAX_VALUE;
		int secondWhenOrdered = Integer.MAX_VALUE;
		
		Set<Integer> elements = new HashSet<>(array.length);
		for(int i = 0; i < array.length; i++) {
			int element = array[i];
			if(element < firstWhenOrdered) {
				secondWhenOrdered = firstWhenOrdered;
				firstWhenOrdered = element;
			} else if (element < secondWhenOrdered) {
				secondWhenOrdered = element;
			}
			elements.add(element);
		}
		
		int commonDifference = secondWhenOrdered - firstWhenOrdered;
		if(commonDifference == 0) return false;	//don't remember whether this should be valid - if so, this algorithm won't work
		int nextElement = secondWhenOrdered + commonDifference;
		for(int i = 2; i < array.length; i++) {
			if(!elements.contains(nextElement))
				return false;
			nextElement += commonDifference;
		}
		
		return true;
	}

public boolean checkArithmeticSequence(int[] array) {
		if(array == null || array.length == 0) return false;	//not a sequence at all
		if(array.length == 1) return true;	//may be considered a sequence, but I would talk to the interviewer
		int firstWhenOrdered = Integer.MAX_VALUE;
		int secondWhenOrdered = Integer.MAX_VALUE;
		
		Set<Integer> elements = new HashSet<>(array.length);
		for(int i = 0; i < array.length; i++) {
			int element = array[i];
			if(element < firstWhenOrdered) {
				secondWhenOrdered = firstWhenOrdered;
				firstWhenOrdered = element;
			} else if (element < secondWhenOrdered) {
				secondWhenOrdered = element;
			}
			elements.add(element);
		}
		
		int commonDifference = secondWhenOrdered - firstWhenOrdered;
		if(commonDifference == 0) return false;	//don't remember whether this should be valid - if so, this algorithm won't work
		int nextElement = secondWhenOrdered + commonDifference;
		for(int i = 2; i < array.length; i++) {
			if(!elements.contains(nextElement))
				return false;
			nextElement += commonDifference;
		}
		
		return true;
	}

boolean isArithemticProgression(int[] nums) {
	    	 if(nums.length <=1)
	    		 	return true;
	    	 int sum = 0;
	    	 int n = nums.length;
	    	 int diff = nums[1] - nums[0];
	    	 int min = Integer.MAX_VALUE;
	    	 for (int num : nums) {
	    		 min = Math.min(num,min);
                         sum += num;
	    	 }
	    	 
	    	 if(sum == (2*min + (n - 1) * diff)*n/2) {
	    		 return true;
	    	 }
	    	 return false;
	     }

A quick solution based on the min-max hint:

public bool CheckArithmeticSequence(int[] a)
{
    if (a.Length == 0 || a.Length == 1)
        return false;

    int min = int.MaxValue;
    int max = int.MinValue;
    int step = 0;
    bool[] seq = new bool[a.Length];

    for (int i = 0; i < a.Length; i++)
    {
        if (min > a[i])
            min = a[i];

        if (max < a[i])
            max = a[i];
    }

    step = (max - min) / (a.Length - 1);

    for (int i = 0; i < a.Length; i++)
    {
        var idx = a[i] / step;
        if (idx >= 0 && idx < a.Length)
            seq[idx] = true;
        else
            return false;//not in the sequence (1,3,5,7,...)
    }

    for (int i = 0; i < seq.Length; i++)
    {
        if (!seq[i])
            return false;//missing an element in the sequence -> duplicates for example
    }

    return true;
}

PHP:

$ar = array(1,5,9,13,17,2);

if (isSeq($ar)) echo "+";
else echo "-";

function isSeq ($ar) {
   if (count($ar)<=1) return true;
   $dif = $ar[1]-$ar[0];
   for ($i=1; $i<count($ar); $i++) {
      if ($ar[$i]-$ar[$i-1]<>$dif) return false;
   }
   return true;
}

the only way to check if a given integer array is arithmetic sequence or not is to sort it. Since the sequence has min and max, then it can be sorted by counting sort. The time complexity is O(n), but need extra space.

c# implementation.
O(n) time.
O(1) space.

private static bool CheckAP( int[] arr ) {

    int[] minmaxs = new int[3]{ int.MaxValue, int.MaxValue, int.MinValue }; //globalMin, secondMin, gloabalMax
    for ( int i = 0; i < arr.Length; i++ ) {
        if ( arr[ i ] == minmaxs[ 0 ] || arr[ i ] == minmaxs[ 2 ] ) {
            return false; // AP cannot contain duplicate elements
        }
        minmaxs[ 1 ] = Math.Max( minmaxs[ 0 ], Math.Min( arr[ i ], minmaxs[ 1 ] ) );
        minmaxs[ 0 ] = Math.Min( arr[ i ], minmaxs[ 0 ] );                
        minmaxs[ 2 ] = Math.Max( arr[ i ], minmaxs[ 2 ] );
    }
    var step = minmaxs[ 1 ] - minmaxs[ 0 ];
    if ( ( minmaxs[ 2 ] - minmaxs[ 0 ] ) / step + 1 != arr.Length ) {
        return false;
    }
    int bit = ( minmaxs[ 0 ] & 1 ) == 1 ? 1 : 0;
    for ( int i = 0; i < arr.Length; i++ ) {
        if ( bit == 0 ) {
            if ( ( ~(arr[ i ] % step) & bit) == 0 ) { continue; }
            return false;
        }
        if ( bit == 1 ) {
            if ( ( (arr[ i ] % step) & bit) == 1 ) { continue; }
            return false;
        }
    }
    return true;
}

{{def array_seq(list1,n):
d=list1[1]-list1[0]
i=2
is_set=1
while i<n:
if list1[i]-list1[i-1]!=d:
is_set=0
break
else:
is_set =1
i+=1
if is_set:
print "True"
else:
print "False"


list1=[]
n=input("enter the no of array element :\n")
for i in range(1,n+1):
list1.append(input())
array_seq(list1,n)

}}

Binary search can be used along with the Arithmetic progression formula a[n] = a+(n-1)d
formula to find it in log(n) time

O(n) time complexity
+ O(n) space for verification

import java.util.HashSet;

public class ArithmeticSequence {

	public static void main(String[] args) {
		int[] array = new int[] {31,21,11,41,61,51,71};
		System.out.println("is Arithmetic ? "+isArithmeticSequence(array));
	}
	
	static boolean isArithmeticSequence(int[] array) {
		if (array.length == 0) 
			return false;
		if (array.length == 1) 
			return true;

		// find minimum element in array
		int min = min(array);
		
		// find the diff between elements as a double
		double diff = diff(array, min);
		// and check if it is an integer
		if (diff != (int)diff) 
			return false;
		
		// if the diff looks valid, verify solution
		return verify(array, (int)diff, min);
	}
	
	static double diff(int[] array, int min) {
		int n = array.length;
		double sum = 0;
		
		for (int i = 0; i < array.length; i++) {
			sum += array[i];
		}
		return (2*sum/n - 2*min)/(n-1);
	}
	
	static boolean verify(int[] array, int diff, int min) {
	
		HashSet<Integer> set = new HashSet<>();
		for (int i:array) set.add(i);
		for (int i:array) {
			if (i != min && !set.contains(i-diff)) {
				return false;
			}
		}
		return true;
	}
	
	static int min(int[] array) {
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < array.length; i++) {
			if (array[i] < min) min = array[i];
		}
		return min;
	}
}

import java.util.Arrays;

public class ArithmeticDemo {
	public static void main(String[] args) {
		int[] arr = {10,8,4,5,6,7};
		Arrays.sort(arr);
		int sum1, sum2 = 0;
		
		for(int a : arr) {sum2 += a;}
		
		sum1 = (arr[0] + arr[arr.length-1]) * arr.length / 2;
		System.out.println(sum1 == sum2);
	}
}

import java.util.Arrays;

public class ArithmeticDemo {
	public static void main(String[] args) {
		int[] arr = {10,8,4,5,6,7};
		Arrays.sort(arr);
		int sum1, sum2 = 0;
		
		for(int a : arr) {sum2 += a;}
		
		sum1 = (arr[0] + arr[arr.length-1]) * arr.length / 2;
		System.out.println(sum1 == sum2);
	}
}

import java.util.Arrays;

public class ArithmeticDemo {
	public static void main(String[] args) {
		int[] arr = {10,8,4,5,6,7};
		Arrays.sort(arr);
		int sum1, sum2 = 0;
		
		for(int a : arr) {sum2 += a;}
		
		sum1 = (arr[0] + arr[arr.length-1]) * arr.length / 2;
		System.out.println(sum1 == sum2);
	}
}

import java.util.Arrays;

public class ArithmeticDemo {
public static void main(String[] args) {
int[] arr = {10,8,4,5,6,7};
Arrays.sort(arr);
int sum1, sum2 = 0;

for(int a : arr) {sum2 += a;}

sum1 = (arr[0] + arr[arr.length-1]) * arr.length / 2;
System.out.println(sum1 == sum2);
}
}

import java.util.Arrays;

public class ArithmeticDemo {
	public static void main(String[] args) {
		int[] arr = {10,8,4,5,6,7};
		Arrays.sort(arr);
		int sum1, sum2 = 0;
		
		for(int a : arr) {sum2 += a;}
		
		sum1 = (arr[0] + arr[arr.length-1]) * arr.length / 2;
		System.out.println(sum1 == sum2);
	}
}
// end

I see some people use the Sum to check if it is a sequence. While Sum is easily commutable knowing the min (first in seq) and max (last in seq) elements by n/2*[min + max]. Even if you match the sum it doesn't mean you have a sequence. Like the two sequences below:

seq1 = 1, 3, 5, 7, 9 (True)
seq2 = 1, 4, 5, 6, 9 (False)

As mentioned by small challenges the best you can get is O(n):
1. Go tru the elements to find min and max and build a hashmap
2. in a loop check if all the elements of the expected sequence exist in the hashmap

O(n) time with extra O(n) space

// Determine if a sequence of non-negative integers is arithmetic.
public class Arithmetic
{
		public static boolean isArithmetic(int[] arr)throws NullPointerException
		{
				if(arr==null)
				{
					throw new NullPointerException();
				}
				if(arr.length==1)
				{
					return true;
				}
				int min=arr[0];
				int max=arr[0];
				for(int i=0;i<arr.length;i++)
				{
					min=Math.min(min,arr[i]);
					max=Math.max(max,arr[i]);
				}
				int diff=(max-min)/(arr.length-1)
				int expSum=0
				int j=1;
				for(int i=min;i<=max && j<=arr.length;i+=diff)
				{
					expSum+=i;
					j++;
				}
				int actSum=0;
				for(int i=0;i<arr.length;i++)
				{
					actSum+=arr[i];
				}
				return actSum==expSum;
		}
		
		public static void main(String[] args)
		{
			int[] arr={3,3};
			System.out.println("sample input: " + Arrays.toString(arr));
			System.out.println("result: " + Arithmetic.isArithmetic(arr));
			arr={1,2,3,4,5};
			System.out.println("sample input: " + Arrays.toString(arr));
			System.out.println("result: " + Arithmetic.isArithmetic(arr));
			arr={1,2,23,4,5};
			System.out.println("sample input: " + Arrays.toString(arr));
			System.out.println("result: " + Arithmetic.isArithmetic(arr));
			
		}
}
//O(n) time, where n is the number of elements.

How about this? It has complexity of O(n) time, since you have to go once through the array.

function isArithmeticSequence(arr){
	var small, large, sum = 0;

	if (arr.length == 0) return false;

	small = large = arr[0];

	for(var i = 0; i < arr.length; i++){
		if (small>arr[i])
			small = arr[i];
		if (large<arr[i])
			large = arr[i];

		sum+=arr[i];
	}

//Using sum of arithmetic series 
	var seqSum = arr.length * (small + large)/2;

	return sum == seqSum;
}

How about this? O(n) time. The check is relays on the sum of arithmetic series by knowing min and max values.

function isArithmeticSequence(arr){
	var small, large, sum = 0;

	if (arr.length == 0) return false;

	small = large = arr[0];

	for(var i = 0; i < arr.length; i++){
		if (small>arr[i])
			small = arr[i];
		if (large<arr[i])
			large = arr[i];

		sum+=arr[i];
	}

//Using sum of arithmetic series 
	var seqSum = arr.length * (small + large)/2;

	return sum == seqSum;
}

How about this? O(n) time. The check is relays on the sum of arithmetic series by knowing min and max values.

function isArithmeticSequence(arr){
var small, large, sum = 0;

if (arr.length == 0) return false;

small = large = arr[0];

for(var i = 0; i < arr.length; i++){
if (small>arr[i])
small = arr[i];
if (large<arr[i])
large = arr[i];

sum+=arr[i];
}

//Using sum of arithmetic series
var seqSum = arr.length * (small + large)/2;

return sum == seqSum;
}

How about this? O(n) time. The check is relays on the sum of arithmetic series by knowing min and max values.

function isArithmeticSequence(arr){
	var small, large, sum = 0;

	if (arr.length == 0) return false;

	small = large = arr[0];

	for(var i = 0; i < arr.length; i++){
		if (small>arr[i])
			small = arr[i];
		if (large<arr[i])
			large = arr[i];

		sum+=arr[i];
	}

//Using sum of arithmetic series 
	var seqSum = arr.length * (small + large)/2;

	return sum == seqSum;
}

How about this? O(n) time. The check is relays on the sum of arithmetic series by knowing min and max values.

function isArithmeticSequence(arr){
	var small, large, sum = 0;

	if (arr.length == 0) return false;

	small = large = arr[0];

	for(var i = 0; i < arr.length; i++){
		if (small>arr[i])
			small = arr[i];
		if (large<arr[i])
			large = arr[i];

		sum+=arr[i];
	}

//Using sum of arithmetic series 
	var seqSum = arr.length * (small + large)/2;

	return sum == seqSum;
}

How about this? It has time O(n), and uses sum of arithmetic series for comparison, relaying on min/max values.

function isArithmeticSequence(arr){
	var small, large, sum = 0;

	if (arr.length == 0) return false;

	small = large = arr[0];

	for(var i = 0; i < arr.length; i++){
		if (small>arr[i])
			small = arr[i];
		if (large<arr[i])
			large = arr[i];

		sum+=arr[i];
	}

//Using sum of arithmetic series 
	var seqSum = arr.length * (small + large)/2;

	return sum == seqSum;
}

This solution has the O(n) time

public boolean isAP(int[] a) {
		int max = Integer.NEGATIVE_INFINITY, min = POSITIVE_INIFINITY;

		// determine max and min 
		// O(n)
		for (int i = 0; i < a.length; i++) {
			if (max < a[i]) max = a[i];
			if (min > a[i]) min = a[i];
		}

		int diff = (max - min)/(a.length - 1);

		boolean[] aa = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			aa[i] = false;
		}

		for (int i = 0; i < a.length; i++) {
			int index = (a[i] - min)/diff;
			if (aa[index]) {
				return false;
			} else {
				aa[index] = true;
			}
		}

		return true;
		
	}

You can find the 2 smallest elements in the array find the positive differences between them. You add the differences with the 2nd smallest and check whether the element is present continue this until the number of elements if the added element is not in the list come out of the program so that there is no common differences between them elements.

Easiest way using arthimatic sequence properties
Time : O(n), Space : O(1)

public boolean checkArrayIsArthimaticSequence(int[] a, int n) {
		int min = findMin(a,n);
		int max = findMax(a,n);
		

		int common_diff = (max - min) / (n - 1);

		// check for allowed maximum
		// for nth term
		int possible_max = min + (n - 1) * common_diff;
		if (possible_max != max)
			return false;

		// check for difference between any elements
		for (int i = 0; i < n - 1; i++) {
			if (Math.abs(a[i] - a[i + 1]) % common_diff != 0)
				return false;
		}

		return true;
	}

private static void checkForAirthmeticSequence() {
int[] a = { 3,8,13,18,23,28 };
int dif = a[1]-a[0];
int len = a.length;
int count = 0;
for(int i=0; i < len-2 ;i++){
if(dif != (a[i+2]-a[i+1])){
count ++;
}
}
if(count == 0){
System.out.println("Given array is Airthmatic Sequence.");
}else{
System.out.println("Given array is Not a Airthmatic Sequence.");
}
}

Using a HashSet we can do it in O(n) time

public bool IsArithmeticSecuence(int[] a)
{
	if (a == null || a.Length < 2)
		return false;

	var hash = new HashSet<int>();
	foreach (var item in a)
		hash.Add(item);

	var inc = Math.Abs(a[0] - a[1]);
	var right = a[0];
	var left = a[0] - inc;

	while (hash.Remove(right))
		right += inc;
	while (hash.Remove(left))
		left -= inc;

	return hash.Count == 0;
}

public static boolean arith(int c[], int a, int b){
	if((b == c.length) && (c.length > 2)) return true;
	if(c[a] > c[b]) return false;
	return airth(c, a+1, b+1);
}

you would pass on a as 0 and b as 1

# Language used : Ruby


puts "Enter the array elements seperated by space"
arr = []
arr = gets.chomp.split(" ")
difference = arr[1].to_i - arr[0].to_i
length = arr.length
flag = 1
length = length.to_i - 1
for i in 1..length
  if (arr[i].to_i - arr[i.to_i - 1].to_i).to_i == difference
    flag = flag.to_i * 1
  else
    flag = 0
  end
end
if flag.to_i == 1
  puts "Yes"
else
  puts "No"
end

Here's a solution in C#. It passed the following test cases:

int[] a = {1,3,7,4,5,2,6,11};
            Assert.IsFalse(Testing.IsArithmeticSeq(a));

            int[] a2 = { 1, 3, 7, 4, 5, 2, 6 };
            Assert.IsTrue(Testing.IsArithmeticSeq(a2));

            int[] a3 = { -1, -3, -7, -4, -5, -2, -6 };
            Assert.IsTrue(Testing.IsArithmeticSeq(a3));

            int[] a4 = { 11,22,44,33  };
            Assert.IsTrue(Testing.IsArithmeticSeq(a4));

            int[] a5 = { 1, 3, 6, 7, 4, 5, 2, 6 };
            Assert.IsFalse(Testing.IsArithmeticSeq(a5));
public static bool IsArithmeticSeq(int[] a)
        {
            int min = int.MaxValue;
            int max = int.MinValue;
            Dictionary<int, int> occurences = new Dictionary<int, int>();

            for (int i = 0; i < a.Length; i++)
            {
                int current = a[i];
                if (occurences.ContainsKey(a[i])) return false;
                if (a[i] < min) min = a[i];
                if (a[i] > max) max = a[i];
                occurences.Add(a[i], 0);
            }

            double factor = (double)(max - min) / (double)(a.Length - 1);

            if (factor != (int)factor) return false;

            for (int i = 0; i < a.Length; i++)
            {
                if (a[i] % factor != 0.0) return false;
            }
            return true;
        }

public class CheckArthSeq {

public static void isArthSeq(int [] a){

Arrays.sort(a);

int diff = a[1]-a[0];
for(int i =0;i<a.length-1;i++){
if(a[i+1]-a[i]!= diff){
System.out.println("List is not in Arthimetic Seq");
return;
}
}
System.out.println("List is in Arthimetic Seq");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a={2,4,10,12,8,6};
isArthSeq(a);

}

}

- Find the min and max
- factor=max-min/length-1
- if factor is not an integer - this is not a sequence
- Go through each element
-- Save element in a map
-- If element is already in map - this is not a sequence
-- if the difference between current and previous is not a multiple of factor or is greater than the factor - it is not a sequence
Otherwise it is a sequence

import java.util.*;

/* 
 Find max element and min element, max-min / (len-1) = common difference
 find min element, insert all min,min+cd,..,max in hashset
 traverse array and see if all in hashset
 if yes, sequence
 else no

 Time and Space Complexity : Both O(n)
 */

class isArithSequence
{
    public static void main(String args[]) {
        HashSet s = new HashSet();
        int a[] = {0,15,75,45,30,60};
        int min = a[0],max =a[0];
        boolean flag = true;
        for(int i=1;i<a.length;i++) {
            if(a[i]>max) {
                max = a[i];
            }
            if(a[i]<min) {
                min = a[i];
            }
        }
        int cD = (max-min)/(a.length-1);
        for(int i=min;i<=max;i=i+cD) {
            s.add(i);
        }
        for(int i=0;i<a.length;i++) {
            if(!s.contains(a[i])) {
                flag = false;
                break;
            }
        }
        System.out.println("Is Arithmetic sequence : "+flag);
    }
}

> - if factor is not an integer - this is not a sequence

Nice observation.

One way of doing this is using the summation of arithmetic sequence, sum=n/2*(min+max) where n is the number of elements.
We do a linear scan over the array and fetch three things, minimum (starting point of sequence), maximum(ending point of the sequence) and the sum of the elements. and return if LHS==RHS. Here is the O(n)- time complexity, O(1) space complexity below in java.

public boolean isAP(int[] arr)
    {
        int sum=arr[0];
        int min=arr[0];
        int max=arr[0];
        for(int i=1;i<arr.length;i++)
        {
            if(arr[i]>max)
                max=arr[i];
            if(arr[i]<min)
                min=arr[i];
            sum+=arr[i];
        }
        return (sum==arr.length*(max+min)/2);
    }

One way of solving this is using the summation formula of Arithmetic sequence
sum = n/2*[min+max]. We do a linear scan of the array and capture three things, minimum, maximum and the sum. and return if LHS == RHS.

public boolean isAP(int[] arr)
    {
        int sum=arr[0];
        int min=arr[0];
        int max=arr[0];
        for(int i=1;i<arr.length;i++)
        {
            if(arr[i]>max)
            {
                max=arr[i];
            }
            if(arr[i]<min)
            {
                min=arr[i];
            }
            sum+=arr[i];
        }
        return (sum==arr.length*(max+min)/2);
    }

One way of solving this is using the summation formula of Arithmetic sequence
sum = n/2*[min+max]. We do a linear scan of the array and capture three things, minimum, maximum and the sum. and return if LHS == RHS.

public boolean isAP(int[] arr)
    {
        int sum=arr[0];
        int min=arr[0];
        int max=arr[0];
        for(int i=1;i<arr.length;i++)
        {
            if(arr[i]>max)
            {
                max=arr[i];
            }
            if(arr[i]<min)
            {
                min=arr[i];
            }
            sum+=arr[i];
        }
        return (sum==arr.length*(max+min)/2);
    }

1. Find first minimum and second minimum element in array (Time: O(n))
Difference of first and second minimum will be the common diff.

2. Hash all the elements of array. (Time: O(n), Space: O(n))

3. In loop, start from minimum number(found in step 1) and keep adding common diff and check whether new number(after adding common diff) exists in array or not. (Time: O(n))

int IsAP(int a[], int n){

	int min_val1, min_val2;

	minimum_2_elements(a,&min_val1,&min_val2);    // function will set min_val1 and min_val2 to lowest and second lowest value in array
	
	diff = min_val2 - min_val1;
	int num= min_val1 + diff;
	int i=0;
	while(i<n-1){
		if( Hash[num] == 1 ){
			num += diff;
			i++;
		}
		else
			return 0;
	}
	return 1;
}

1. Find first minimum and second minimum element in array (Time: O(n))
Difference of first and second minimum will be the common diff.

2. Hash all the elements of array. (Time: O(n), Space: O(n))

3. In loop, start from minimum number(found in step 1) and keep adding common diff and check whether new number(after adding common diff) exists in array or not. (Time: O(n))

int IsAP(int a[], int n){

	int min_val1, min_val2;

	minimum_2_elements(a,&min_val1,&min_val2);    // function will set min_val1 and min_val2 to lowest and second lowest value in array
	
	diff = min_val2 - min_val1;
	int num= min_val1 + diff;
	int i=0;
	while(i<n-1){
		if( Hash[num] == 1 ){
			num += diff;
			i++;
		}
		else
			return 0;
	}
	return 1;
}

1. Find first minimum and second minimum element in array (Time: O(n))
Difference of first and second minimum will be the common diff.

2. Hash all the elements of array. (Time: O(n), Space: O(n))

3. In loop, start from minimum number(found in step 1) and keep adding common diff and check whether new number(after adding common diff) exists in array or not. (Time: O(n))

int IsAP(int a[], int n){

	int min_val1, min_val2;

	minimum_2_elements(a,&min_val1,&min_val2);    // function will set min_val1 and min_val2 to lowest and second lowest value in array
	
	diff = min_val2 - min_val1;
	int num= min_val1 + diff;
	int i=0;
	while(i<n-1){
		if( Hash[num] == 1 ){
			num += diff;
			i++;
		}
		else
			return 0;
	}
	return 1;
}

Probably we can use the Summation formula for Arithmetic series to find if the given sequence is arithmetic or not?

S= n/2(2*a + (n-1)d)

Steps:
- Find the smallest & second smallest element in the array
- Now you have a and d.
- Also calculate the sum of the all the elements in array.
- Check if sum of the array elements is same as the sum you get using formula.

For Base Cases:
if array size is 1 then just return true

O(1) memory, O(n) time, no sorting needed

def is_arithmetic(arr):
    lo = min(arr)
    hi = max(arr)
    n = len(arr)

    d = (hi - lo)/(n-1)

    print lo, hi, n, d
    diff = 0

    for i in range(lo, hi+1, d):
        diff ^= i

    for i in range(n):
        diff ^= arr[i]

    return diff == 0

Time Complexity: O(n)
Space Complexity: O(1)
1. Find the minimum and maximum elements in the array.
2. Find the value of n/2*(amin + amax)
3. Find the sum of all the elements of the array.
If the values of steps 2 and 3 match, then it is an arithmetic sequence, else not an arithmetic sequence.

public class Main {

public static void main(String[] args) {
int a[] = { 1,5,7 };
int n = a.length;
if(n < 3) System.out.println("Is a seq");
else {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int flag = 0;
for (int i = 0; i < n; i++) {
max = (a[i] > max) ? a[i] : max;
min = (a[i] < min) ? a[i] : min;
}
int d = (max - min) / (n - 1);

for (int i = 1; i < n; i++) {
if (Math.abs(a[i] - a[i - 1]) % d != 0) flag = 1;
}

if (flag == 0)
System.out.println("Is a seq");
else System.out.println("Is not a seq");
}
}
}

private static void checkForAirthmeticSequence() {
		int[] a = { 3,8,13,18,23,28 };		
		int dif = a[1]-a[0];
		int len = a.length;	
		int count = 0;		
		for(int i=0; i < len-2 ;i++){		
				if(dif != (a[i+2]-a[i+1])){
					count ++;
				}		
		}
		if(count == 0){
			System.out.println("Given array is Airthmatic Sequence.");
		}else{
			System.out.println("Given array is Not a Airthmatic Sequence.");
		}		
	}