Check if an Array is Formed by Consecutive Integers

Given an array of integers, check if an array is formed by consecutive integers.

 

For example,


Input:  { -1, 5, 4, 2, 0, 3, 1 }

Output: Array contains consecutive integers from -1 to 5
 

Input:  { 4, 2, 4, 3, 1 }

Output: Array do not contain consecutive integers as element 4 is repeated

 

Approach 1:

 

In order for an array to contain consecutive integers,

  1. The difference between maximum and minimum element in it should be exactly n-1.
     
  2. All elements in the array should be distinct (we can check this by inserting the elements in set or using a visited array).

C++

Download   Run Code

Output:

Array contains consecutive integers

Java

Download   Run Code

Output:

Array contains consecutive integers

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

 

Approach 2:

 

We can check if an array contains consecutive integers by inserting all elements of the array in set and

  1. Check if all elements are distinct (we can check this while inserting the elements in set).
     
  2. Check if difference between consecutive elements in the set is 1 as set stores the elements in sorted order.

C++

Download   Run Code

Output:

Array contains consecutive integers

Java

Download   Run Code

Output:

Array contains consecutive integers

 
The time complexity of above solution is O(nlog(n)) and auxiliary space used by the program is O(n).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
asd
Guest

it can be solved by maths, if it is repeating it should form an arthimetic progression.
Calculate sum of array , and validate below formula

s = 2*a + (n-1)*d.
a = first term.
d = 1

Kundan
Guest

That will fail for many inputs. Total sum can easily be manipulated, we need to validate the individual elements.

nnn
Guest

For Approach 2, shouldn’t it be o(n * log(n)) for the asymptotic complexity? o(n)’s not accurate. If it was, then sorting would be o(n)!