8

Given an unsorted array of numbers, write a function that returns true if array consists of consecutive numbers.

Examples:

  1. If array is {5, 2, 3, 1, 4}, then the function should return true because the array has consecutive numbers from 1 to 5.

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

  3. If the array is {34, 23, 52, 12, 3 }, then the function should return false because the elements are not consecutive.

  4. If the array is {7, 6, 5, 5, 3, 4}, then the function should return false because 5 and 5 are not consecutive.

I came up with the following algo:

  1. find the max and min of the array

  2. max-min+1 should be the size of array

  3. check for duplicates

  4. check for all consecutive numbers in between

How can I achieve the 4th path? (The complexity should be O(n))

Other suggestions are most welcome.

garima
  • 5,154
  • 11
  • 46
  • 77
  • 1
    How exactly do you propose to carry out step 3 in O(n) time in an unsorted array? – NPE Mar 24 '11 at 18:15
  • @aix, if the numbers were random you couldn't. But you can take advantage of their special property (being consecutive) to get a solution. – Mark Ransom Mar 24 '11 at 21:30
  • 2
    If you already verified the **2nd path** and the **3rd path** you don't need the 4th path: it's automatic. – pmg Mar 24 '11 at 22:21
  • Exact dup of http://stackoverflow.com/questions/177118/algorithm-to-determine-if-array-contains-n-nm – xan Mar 25 '11 at 12:31

8 Answers8

18

If the input array is A:

  1. Find the minimum and maximum values of A, return False if the array is of the wrong size.

  2. Create a new array, B, of the same size, initially with all zeroes

  3. For each index i, let B[A[i] - min] = 1.

  4. Check to see if B still contains any zeroes.

Each step takes O(n) time.

Seth
  • 772
  • 5
  • 13
  • Nice. Needs bounds checking in step 3. Also, could be slightly refined by changing step 3 to "increment B[A[i] - min] and return `false` if the result exceeds 1". – NPE Mar 24 '11 at 18:13
  • @aix - Good suggestions. I added the bound check in Step one, but either place would work. – Seth Mar 24 '11 at 18:15
  • Just a small note... you will want to check for using an array index that is out of bounds on step 3. I know its nitpicky, but I've had interviewers criticize me for leaving out simple checks for simplicity. – gnomed Mar 24 '11 at 18:16
  • 1
    @aix, @gnomed: doesn't need bounds checking, B was allocated with size `max-min+1`, so any index `A[i]-min` is in range. You do need to check at step 2, though, that you aren't about to allocate an array of size 0 because max = (U)INT_MAX and min = (U)INT_MIN. – Steve Jessop Mar 24 '11 at 18:17
  • @Steve - I added the "find maximum and check to see if the array is the wrong size bit" after aix made his/her comment. – Seth Mar 24 '11 at 18:19
  • You don't need step 4 if in step 3 you check to see if B[A[i]] is already 1. If so, then you must return false. If this never happens, then (since B and A are the same size) by the pidgeonhole principle B contains only ones. – Joren Mar 24 '11 at 18:23
  • "You do need to check at step 2" - hang on, no you don't, because if the initial array A was size 0 then that wouldn't happen. So overflow isn't a danger provided we use the right types everywhere, and we've probably already specially handled the size 0 case when we tried to find the max/min. – Steve Jessop Mar 24 '11 at 18:25
2
bool consecutive(int a[], size_t n)
{
    int min = find_min(a,n);
    int max = find_max(a,n);

    if (max - min + 1 == n) {
        // variant of counting sort, O(n)
        // note: never freed, don't use in production
        int *freq = calloc(sizeof(int), n);

        for (size_t i=0; i<n; i++)
            if (++freq[a[i] - min] > 1)
                return false;
        return true;
    }
    return false;
}
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • You can safe a factor of 32 (or whatever the word size is) on your if you use `freq` as a bit vector instead of a count. More simply, you could save a factor of ~4 if you just use an array of `uint8_t`. – Thomas M. DuBuisson Mar 24 '11 at 20:55
  • @TomMD: that's right. But I was only aiming for O(n) complexity. – Fred Foo Mar 24 '11 at 21:14
2
int visited[max - min + 1];

for(c = min; c <= max; c++) {
    visited[array[c] - min] += 1;

    if(visited[array] > 1)
        return false;               // since this is a duplicate
}

This should be ok. visited[] keeps trace of how many times a number from original array appeared. If any of its elements is greater than two there's a duplicate, so return false; Since the size of both arrays is max-min+1 at the end of the loop visited[] is full, because we visited all elements of array[]. So it visited is empty, there must be a duplicate somewhere, but we don't need to bother because at that time we're still returned false.

BlackBear
  • 22,411
  • 10
  • 48
  • 86
2

It seems to me this can be done in O(n) time with O(1) additional space.

Determine min and max of the array. If (max - min + 1) != n, return false.

Subtract min from each element in the array. We now have an array with n elements from the range [0, n). We now just have to check for duplicates. That can be done in linear time (each element is moved at most once) by code like the following:

for (int i = 0; i != n; ++i)
{
    if (A[i] != i)
    {
        int temp = A[i];
        for (;;)
        {
            int index = temp;
            if (A[index] == index)
            {
                // We have a duplicate
                return false;
            }
            std::swap(temp, A[index]);
            if (index == i)
            {
                // A[i] now contains i
                break;
            }
        }
    }
}
// If we get to here, there are no duplicates
user515430
  • 3,341
  • 2
  • 17
  • 13
  • Correct, but you don't need to work so hard in the first `if`. Just place `a[i]`. `if (a[i]!=i) { if (a[a[i]]==i) return false; else std::swap(a[i], a[a[i]]); }` No loop within a loop, but perhaps more array subscripting. It might look even nicer to always swap and make another pass to check for dups. – xan Mar 25 '11 at 01:15
  • @xan - I think you meant `if (a[a[i]] == a[i]) return false;` I still think you need an inner loop. Try with A = {2, 0, 3, 4, 1}. – user515430 Mar 25 '11 at 11:16
  • @user515430 You're right -- thanks for the counter-example. Another try for a single loop: `i=0; while(i – xan Mar 25 '11 at 12:26
0

I'm not too good at C, but do you need to do step 4? Surely if 2 is true and there are no duplicates then it contains the sequence, otherwise it doesn't?

Dean Barnes
  • 2,252
  • 4
  • 29
  • 53
0

As asked by you, the 4th step in your algo is not needed at all (as #2 and #3 will guarantee that they are consecutive)

We can save many more comparisons(to improve its time complexity) of the algo by doing all the steps in a single traverse:

int is_consecutive(int *a, int size)  // O(n) algo
{   
 int min, max;
 hash H;
 if(!a || size == 0 ) return -1;
 max=min=a[0];
 H.insert(a[0]);

 for(i=1; i<size; i++) {
   if(H.find(a[i]) { delete H; return 0; }  // duplicacy check
   else H.insert(a[i]);
   if(a[i] < min) min = a[i];
   else if(a[i] > max) max = a[i];
 }
 if(size != (max - min)) { delete H; return 0; }  //range = size check
 delete H;   
 return 1;
}
pankiii
  • 435
  • 3
  • 9
-2

Find min element,Max element and sum of elements in the array.

They form an Arthematic Progression and sum of elements is: (no.Of element/2)*(2*minElement+(n-1)*differnce)

difference is 1 in this case

if sum==(array.length/2)*(2*minElement+(array.length-1)*1) && maxElement==(minElement+(lenght ofArray-1)*1)

Then the numbers are consecutive.

There is no additional space complexity and time complexity is O(n)

Thanks @jpalecek for correcting. This should be fine now

Tejas
  • 17
  • 4
-2

Here's something that works for 1..N, you can just use the arithemtic series forumulae to adjust for this [i,i+n]

// gcc -Wall q1.cc -o q1 && q1                                                                          

//Given an array of size N in which every number is between 1 and N, write a simple program to determine
//if there are any duplicates in it.                                                                    

//answer                                                                                                
/* The numbers can be assumed to not be stored in sorted order.  We also assume that all numbers are    
between 1 and N inclusive.  If for example they are not, then we will return true indicating that there 
is a possibility of a duplicate.                                                                        

This can be implemented using a bit array of size N all initialized to 0.  as we iterate the input array
of numbers, we simply check if the bit array at that number index is set, if so, we return true.  if not
we set the bit.  we loop until we get to the end of the list, and if we get there, that means no        
duplicate was found, and we can return false.                                                           

However, the above algorithm has the problem of using extra space.  A better idea is to take advantage  
of the fact that we are guaranteed that the numbers are between 1 and N.  if we were to use the fact    
that the arithmetic sum of these numbers is equal to n(n+1)/2, then we can just sum up all the numbers  
and ensure that it equals the above sum.  If it does, we have no duplicate, else we do.                 
*/                                                                                                      

#include <stdio.h>                                                                                      
#include <assert.h>                                                                                     

bool any_dup(const int *a, int n)                                                                       
{                                                                                                       
        int req_sum = n*(n+1)/2;                                                                        

        int s = 0;                                                                                      
        for (int i = 0;i<n;i++)                                                                         
                s += a[i];                                                                              

        return (s != req_sum);                                                                          
}                                                                                                       


int main()                                                                                              
{                                                                                                       
        int a[]={1,2,3,4,5};                                                                            
        assert(!any_dup(a,5));                                                                          

        int b[]={1,2,2,3,3,4,5,6};                                                                      
        assert(any_dup(b,8));                                                                           

        int c[]={5,2,3,1,4};                                                                            
        assert(!any_dup(c,5));                                                                          

        int d[]={34,21,1,4,2};                                                                          
        assert(any_dup(d,5));                                                                           

        return 0;                                                                                       
}
lateralpunk
  • 221
  • 2
  • 2