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

duplicate k liye dusra solution kam nahi karega yaar

Why?

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

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.

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…

No. Duplicates are not allowed.

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

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.

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.

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.

Frankly, I don’t know squat about math.

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.

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)

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.

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.

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