Sunday, March 11, 2012

Check if Array elements are consecutive

Given an unsorted array of numbers, write a function that returns true if array consists of consecutive numbers. 
Examples:
a) If array is {5, 2, 3, 1, 4}, then the function should return true because the array has consecutive numbers from 1 to 5.
b) If array is {83, 78, 80, 81, 79, 82}, then the function should return true because the array has consecutive numbers from 78 to 83.
c) If the array is {34, 23, 52, 12, 3 }, then the function should return false because the elements are not consecutive.
d) If the array is {7, 6, 5, 5, 3, 4}, then the function should return false because 5 and 5 are not consecutive.
http://algorithms.tutorialhorizon.com/check-if-array-is-consecutive-integers/

http://www.geeksforgeeks.org/check-if-array-elements-are-consecutive/

Approach:
Method 1:Visited Array

The idea is to check for following two conditions. If following two conditions are true, then return true.
1) max – min + 1 = n where max is the maximum element in array, min is minimum element in array and n is the number of elements in array.
2) All elements are distinct.

To check if all elements are distinct, we can create a visited[] array of size n. 
We can map the ith element of input array arr[] to visited array by using arr[i] – min 
as index in visited[].

Method 2:Mark Negative
 This method is O(n) time complexity and O(1) extra space, but it changes the original 
array and it works only if all numbers are positive. We can get the original array by 
adding an extra step though. It is an extension of method 2 and it has the same two steps.

1) max – min + 1 = n where max is the maximum element in array, min is minimum element 
in array and n is the number of elements in array.
2) All elements are distinct.

In this method, the implementation of step 2 differs from method 2. Instead of creating a 
new array, we modify the input array arr[] to keep track of visited elements. 
The idea is to traverse the array and for each index i (where 0 <= i < n), 
make arr[arr[i] – min]] as a negative value. If we see a negative value again then there 
is repetition. 

No comments:

Post a Comment