Ex: Input: 1 2 5 3 6 8 7
Output: 5 6 7 8
As given in Above example we need to find Longest Consecutive sequence in O(n)
I have implemented in O(n) considering by creating hash of data type bool.
Logic :
1) Create a function
2) Pass initial values one by one to this function and length.
3) What function does ?
Answer : it checks the longest possible consecutive sequence in array
How : pass 1, function will check whether 2 is there is array,
if present increase count and pass 2 to same function.
else return length.
4) get maximum such length and last passed index for which maximum such length is there.
5) Print from max index till the length.
example :
function will return Index, Count as
1-3
2-2
5-4 //max
3-1
6-3
8-1
7-2
PS : To optimize search in hash for sequential search, we can use dynamic programming which may cause extra space. hence here we have not used it. else People are welcome to share Solution with DP
Thanks to Dhaval for suggesting this approach and Article
Code
#include <stdio.h>
#include <stdbool.h>
#define gc getchar_unlocked
#define pc putchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<‘0’||c>’9′)c=gc();while(c<=’9’&&c>=’0’)n=(n<<1)+(n<<3)+c-‘0’,c=gc();return n;}
bool c[100001]={0};
int findLongestsequence(int a, int count){
int st=a,i,j;
a++;
if(c[a]==1){return(findLongestsequence(a,++count));}
return count;
}//findLongestsequence
int main(void){
int i=0,j,t,n,st,len,count=1,maxcount=1,maxseq=-1;
len=scan();
j=len;
int a[len];
while(j–){
a[i]=scan();
c[a[i]]=1; //creating hash with value pair same
i++;
}
printf(“Entered String :”);
for(i=0;i<len;i++){printf(“%d “,a[i]);}
for(i=0;i<len;i++){
count = findLongestsequence(a[i],count);
if(count > maxcount ){
maxcount= count;
maxseq = a[i] ;
}
count=1;
}
//printf(“nSt and Len : %d & %dn”,maxseq,maxcount);
printf(“nMaximum Consequitve string “);
while(maxcount–) printf(“%d “,maxseq++);
return 0;
}
You can find working code at : http://ideone.com/8xODTn