Amazon Interview Question
Software DevelopersCountry: United States
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...
I was asked this in an interview. I asked if I could sort it and the see if it is an arithmetic sequence or not (by calculating the difference between i+1 and i).
He didn't seem satisfied with the sorting approach. I tried to see if I can do something by calculating the min and max value - he said I am in the right direction. But unfortunately, I couldn't solve it and asked him for a hint. He gave me this:
(max - min)/(len - 1) = difference
(70 - 10)/(7 - 1)
60/6 = 10
Its pretty straight forward to solve if the array can be stored.
I see what he is is hinting at....he says take the sum of all the elements in the array and subtract the diff...but that in itself would not prove a series....
Post a tiny walk before coming to my desk, I had a slightly diff solution. Find the lowest two elements in pass 1. From their difference, you know the diff that every adjacent element should satisfy. I would insert all the elements into a hash and then for each element, check the existence of the element+diff in the hash. This would be pass 2. Hitting an already paired element would invalidate the series as would not finding the adjacent element.
What do you think about this? O(n) but needs some extra memory.
Yeah. That is exactly what I started to do (But couldn't finish due to lack of time) ! I also think thats the best way to do!
Thanks,
pavi
If the hint was to find min and max then one way is to check if (min+max)*n/2 is equal to sum of the array then it is a ap else not.
Find min and max in O(n)
(max - min)/(len -1) = X.
Then for each element in the array check
element - min = multiple of X,
if all of them satisfy this, then array is a arithmetic sequence
otherwise no.
Solution is O(2n)
seems like finding the diff is a very good idea, then you can create lookup table and whenever you see a proper value(min+diff*k), mark it in the array and next occurrence of the same value will invalidate the sequence. If the visited value is not a proper one, just return invalid.
Time complexity is O(n)
Space complexity is O(n)
Once we know the difference btw consecutive elements in the series we could try to sort the array, that is rearranging the elements according to their positions in the arithm series. If we fail to do this, this proves that the array is not sequence
In other words, an element ai goes to the position j = (ai - amin) / diff. That should work in a linear time
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;
}
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);
}
}
// end
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;
}
# 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);
}
}
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
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.");
}
}
1) Find the min and max.
- Anonymous February 10, 20162) 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