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

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

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;

Open in new window

0
tjgquicken
Asked:
tjgquicken
  • 2
  • 2
  • 2
1 Solution
 
Kyle AbrahamsSenior .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  i is your index:

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
 
MageWindCommented:
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;
}

Open in new window

0
 
MageWindCommented:
oops!  the "prev = current" should be moved up one line--it should be inside of the last brace.
0
Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

 
phoffricCommented:
How about including all your source code?

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
 
phoffricCommented:
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
 
Kyle AbrahamsSenior .Net DeveloperCommented:
phoffric . . . you are correct and thank you for pointing out the error.    

Does the author need further assistance?
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

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