Solved

# Algorithm for finding consecutive elements from a set

Posted on 2009-12-17
628 Views
I'm trying to write a short function/procedure/algorithm that takes as input a set S of n integers and a positive integer 1 < k <= n and returns true iff there's a subset of S with k consecutive numbers. I'm also trying to find an algorithm that will solve this problem in place, without allocating memory for another data structure for sorting the set. The best I can think of so far is an algorithm that runs in n^2 time, but I'm wondering if it's possible to do better.

I have my code (Java) below, but if anybody could point out any possible time/memory improvements I'd appreciate it. Thanks.
``````for(Iterator<Integer> iter1 = s.iterator(); iter1.hasNext(); ) {
int x = 0, b = iter.next();
for(Iterator<Integer> iter2 = s.iterator(); iter2.hasNext(); ) {
x |= (1 << iter2.next() - b);
}
if((1 << k) - 1 == x) {
return true;
}
}
return false;
``````
0
Question by:tjgquicken

LVL 39

Accepted Solution

For a search like that you're better off doing a sort first.  (you don't need more memory you can sort in place with a Binary Tree Sort:
http://en.wikipedia.org/wiki/Binary_tree_sort

From there your search  gets better as you only need to check every kth' element, then do a check in between  (assuming you have a previous as well.)

if  (S[i] + K-1 != S[i+K-1] )
// not possible to be consecutive.
i = i+K-1 ;
else
//check in between.

Efficiency grows as K increases.

0

LVL 3

Expert Comment

I hope this works =D
``````//I have not tested this code, but something of the like should work

private boolean areConsecutives (int[] s, int k) {

int prev int; //The previous integer

int countConsec = 0; //The number of integers in a row

prev = s[0]

for (int current = 1; current < s.length; current++) {

if (prev + 1 == current)) {

countConsec++;

if (countConsec >= k)

return true;

} else

countConsec = 0

}

prev = current;

}
``````
0

LVL 3

Expert Comment

oops!  the "prev = current" should be moved up one line--it should be inside of the last brace.
0

LVL 31

Expert Comment

From the three solutions (your snippet and two other offerings), it is not clear to me what the requirements are. So, here is an example, and you tell me the expected answer.
k = 5
S = {9,2,3,4,8,12,10,11,22,44}

CASE A: No pre-sorting:
If we scan S in order of element appearance, then the largest value of consecutive numbers is 3; namely, {2,3,4}; and the test fails to meet the requirement of k=5.

CASE B: pre-sorting:
If we sort S, then we get:
SSort = {2,3,4,8,9,10,11,12,22,44}
Now, the longest consecutive sequence is {8,9,10,11,12}, whose length is 5; so the test is a success.

Which scenario are you looking for: CASE A or B?

Also, could you comment in detail what the following is doing? Maybe a simple numerical example illustrating this would help.

x |= (1 << iter2.next() - b);       <------- shifting?? bit operations??
}
if((1 << k) - 1 == x) {  <------ shifting??
0

LVL 31

Expert Comment

In the first post:

if  (S[i] + K-1 != S[i+K-1] )  <-------- There was a mismatch, so agree that not consecutive starting from i
// not possible to be consecutive.
i = i+K-1 ;                       <-------- So, how is it that we can skip K-1 elements?

Suppose k=5 and S = {1,3,4,5,6,7,11,12}
When i=0, S[0] is 1.
(S[i] + K-1 != S[i+K-1] ) ---> (1 + 5-1 != S[0+5-1] ) -->  ( 5 != S[4] ) -->  ( 5 != 6 )
So, i = i+K-1 --> 0 = 0+5-1 --> i = 4; but S[4] = 6; but correct answer has sequence starting at i=1.

else                               <--------- We have the expected end point so agree that
//check in between.      <-------- we must make sure consecutive in between
0

LVL 39

Expert Comment

phoffric . . . you are correct and thank you for pointing out the error.

Does the author need further assistance?
0

## Featured Post

### Suggested Solutions

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…