Problem
Given a set of numbers, find the longest subset with consecutive numbers be it any order.
Input:
S = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3}
we have 2 consecutive sets
s1 = {1, 2, 3, 4, 5}
s2 = { 8, 9, 10, 11}
Ans.
s1 = {1, 2, 3, 4, 5}
Solution
Sort the array
Find the longest subset
Remove duplicate numbers
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the longest subset with consecutive numbers be it any order.
Created Date : 15-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
void FindLongestSubset(int* s, int len, int* subs, int& slen)
{
sort(s, s + len);
copy(s, s + len, ostream_iterator<int>(cout, " "));
cout << endl;
int* p(s);
int* start(NULL);
int l(0); // length
int maxLen(0);
int *maxStart(NULL);
int *pSubs(subs);
while(p < s + len){
if(start == NULL){
start = p ++;
l ++;
}
else{
if(*p - *(p-1) == 1){
l ++;
}
else{
l = 0;
start = NULL;
}
p ++;
while(p < s + len && *p == *(p - 1)){
p ++;
}
}
if(l > maxLen){
maxLen = l;
maxStart = start;
}
}
// Copy elements to the subset
l = 0;
while(l < maxLen){
*pSubs ++ = *maxStart ++;
while(maxStart < s + len && *maxStart == *(maxStart - 1)){
maxStart ++;
}
l ++;
}
slen = maxLen;
}
int main(int argc, char* argv[])
{
int testCase[] = { 5, 1, 9, 3, 8, 20, 4, 10, 2, 11, 3, 12, 13, 14, 12, 12, 11};
int len(sizeof(testCase)/sizeof(testCase[0]));
cout << "Then test case is " << endl;
copy(testCase, testCase + len, ostream_iterator<int>(cout, " "));
cout << endl;
int *subs = new int[len];
int sLen(0);
FindLongestSubset(testCase, len, subs, sLen);
cout << "The longest subset with consecutive numbers is" << endl;
copy(subs, subs + sLen, ostream_iterator<int>(cout, " "));
cout << endl;
delete[] subs;
return 0;
}
Output
Then test case is
5 1 9 3 8 20 4 10 2 11 3 12 13 14 12 12 11
1 2 3 3 4 5 8 9 10 11 11 12 12 12 13 14 20
The longest subset with consecutive numbers is
9 10 11 12 13 14
Press any key to continue . . .