Home > Applied Algorithms, Arrays, Sorting > Find if a given array is a sequence of consecutive integers.

Find if a given array is a sequence of consecutive integers.

Problem Statement: You have been given an array of positive integers, obviously, in a random order. You are supposed to find if all elements taken can form a sequence of consecutive integers. (Array might have duplicates, but then it is not correct)

Sorting (approach 1) might be the first solution that pops up in everyone’s mind. Well, that would take O(n lg n) time using the best algorithms out there. What if we want to do it in O(n) time?

You will then tell me to find the MIN and MAX of the array, make another array (with default value 0) and increment the corresponding value in this array when you discover such elements. That is your concept of counting (approach 2), if you remember. You achieved time complexity O(n) but added space complexity O(n). Now you might struggle to reduce this space complexity.

EDIT: I’ll try come up with a better solution shortly. (Forget the one that used to be here)

Have fun!

Advertisements
  1. futurenaut(25 min)
    October 23, 2011 at 10:24 am

    duplicate k liye dusra solution kam nahi karega yaar

  2. October 24, 2011 at 3:45 am

    Try the third algorithm on [1, 1, 3, 4, 5, 8, 7, 8, 8, 10]?

    Btw, congrats for Microsoft!

    One problem that has me stumped (from Skiena):

    You have to construct a binary search tree with keys k[i], with the probability of accessing k[i] being p[i]. Once you have the binary tree, traversing to the left (from any node) costs A, and traversing to the right costs B. How do you construct the tree such that the total cost of access (w.r.t. the given probabilities) is minimum?

    It smells like constructing a Huffman encoding, but I’m unable to break down the problem properly. Perhaps you’ll be able to solve it. 🙂

    • October 24, 2011 at 9:00 am

      The third algorithm will work for it because we are maintaining the PRODUCT variable as well 🙂

      Thanks for the wishes! 🙂 I’ll try to get back with the solution very soon.

  3. October 24, 2011 at 5:46 am

    1 1 2 3 4 5….sir is this sequence correct according to question?…If yes then I have some modification for the algorithm which will make it to work for duplicates too…

  4. October 24, 2011 at 9:06 am

    Both the product and sum come out to be correct in the example case I gave. That is the point.

    • October 24, 2011 at 9:31 am

      Right. I got your point. I had to modify the algorithm a little for that. We were taking sums of (MAX-A[i]). Do the same for PRODUCT. (Earlier I was doing it with MAX-A[i]+1). The only thing you need to take care is that you shouldn’t multiply the PRODUCT with 0 (when your A[i] = MAX).

      Modified the post accordingly. Take a look and tell me if I am missing something.

  5. October 24, 2011 at 3:51 pm

    I don’t think this modified approach will work either (I’m too lazy to come up with a test case now :P). The reason is this:

    You’re basically trying to calculate P, and S for the numbers x(0), x(1) … x(n – 1) such that:

    x(0) + x(1) + … + x(n – 1) = S
    x(0) * x(1) * … * x(n – 1) = P

    and then you’re trying the predict the value for x(0), x(1) … based the values of P and S. But, in general, the above equations will have multiple solutions for some values of P and S and n > 2 (since variables > equations). There simply isn’t enough information in the product and sum of a set of numbers to conclude their individual values.

    • October 24, 2011 at 5:40 pm

      Can’t argue with a mathematician 🙂 And yeah, you are right. I guess I’ll have to come up with a better approach to solving this.

  6. October 24, 2011 at 5:44 pm

    Frankly, I don’t know squat about math.

    • October 24, 2011 at 5:48 pm

      Lol. You know what (and I am not sure), in the method I was talking about, checking the array for duplicates and making sure that the number of elements in the array = MAX-MIN+1 might remove those test cases which give the wrong answers. I’ll have to think about it. But on first thoughts, these 2 restraints might work. As you can see, I am no good at Math either.

  7. Anup
    October 29, 2011 at 1:19 pm

    ummmm ..
    How about this..

    First, find the sum of all the elements in the array. Store it in ActualSum. : O(n)

    Secondly, in one traversal, find the maximum and the minimum.: O(n)

    We know the formula for sum of first N numbers. i.e. ( n*(n+1) / 2 )

    so do that for max: ( max*(max+1) ) / 2 and store it in MaxSum
    and for min: ( min*(min+1) ) / 2 and store it in MinSum

    so if ( (MaxSum – MinSum) + 1 ) == ActualSum

    You have an array of consecutive numbers.
    if not, you don’t, or you have dups in the array.

    Total Complexity: O(n)

    • October 29, 2011 at 3:38 pm

      Yeah I thought of that (+ maintaining a variable PRODUCT). However, for a large number of variables, that method will fail. Please see the discussion between me and Sanjoy in the comments above. You should be able to understand.

  8. Anup
    October 30, 2011 at 7:28 am

    Apologies.. I commented through a custom blog reader so didn’t see any of the above comments..
    Do you have a counter example as to how it will fail for for a large input set?
    From what I gather about the problem, its precarious restrictions are screaming for the aforementioned approach.

    • October 30, 2011 at 9:25 am

      There is an example Sanjoy has given in one of his comments. Try it out. And he explains the same later.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: