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++ implementation –
 

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++ implementation –
 

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).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
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
Kundan

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)!

wpDiscuz