[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 636

Algorithm for finding consecutive elements from a set

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
tjgquicken
• 2
• 2
• 2
1 Solution

Senior .Net DeveloperCommented:
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

Commented:
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

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

Commented:

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

Commented:
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

Senior .Net DeveloperCommented:
phoffric . . . you are correct and thank you for pointing out the error.

Does the author need further assistance?
0

Featured Post

• 2
• 2
• 2
Tackle projects and never again get stuck behind a technical roadblock.