# [Week Seven] Programming Contest - Longest Sequence

Welcome back to week seven of the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This weeks challenge is to write a method that takes in a non-empty integer array and returns the length of the longest sequence of consecutive integers after the array has been sorted. You can assume that there are not repeated elements in the array.

Examples:

longest({}) -> 0
longest({5}) -> 1
longest({3, 6, 2, 9}) -> 2
longest({3, 6, 2, 9, 29, 30, 31}) -> 3
longest({1, 3, 5, 8, 7, 9, 10, 11, 121}) -> 5
longest({-1, 3, 2, 1, -2, 0}) -> 6

Imports are allowed for this challenge!

Challenge Closes: Sunday 12/20/15

Good luck!

Would `longest({5})` return 1 or 0?

Edit:
If returning 0 is correct then I’ll submit this: (it’s not)

``````public static int l(int[]a){Arrays.sort(a);int m=0,i=1,c=1,l;while(i<a.length){l=a[i-1];c=(l+1==a[i++])?c+1:1;if(c>m)m=c;}return m;}
``````

132 Characters (138 if the method name needs to be `longest`)

``````public static int longest(int[] array) {
Arrays.sort(array);
int max = 0, i = 1, count= 1, last;

while (i < array.length) {
last = array[i - 1];
count = (last + 1 == array[i++]) ? count + 1 : 1;
if (count > max) max = count;
}

return max;
}
``````

Python again:
###Short: 192 chars

``````def l(i):
i,s=sorted(i),len(i)
if s:
l,c=1,1
for j in range(1,s):
if i[j-1]==i[j]-1:
c+=1
else:
if l<c:
l=c
c=1
if l<c:
l=c
return l
return 0
``````

``````def longest(intList):
intList = sorted(intList)
if len(intList):
longest, conseq = 1, 1
for i in range(1,len(intList)):
if intList[i-1] == intList[i]-1:
conseq += 1
else:
if longest < conseq:
longest = conseq
conseq = 1
if longest < conseq:
longest = conseq
return longest
return 0
``````

Edit: Hmm. Seems markdown doesn’t work between two code blocks? Tried h3 tag and dashes as well.

you need new lines between markdown and code blocks

Since {} has a sequence length of zero, I think {5} should definitely be one. Iv’e added the case in the examples as well.

There are double linebreaks both before and after that line.

I’ve updated mine, so `longest({5})` returns 1 now. It’s 14 chars larger now… Damn you @kmecpp!!

``````public static int l(int[]a){Arrays.sort(a);int m,i=1,c=1,l,b=a.length;m=(b>0)?1:0;while(i<b){l=a[i-1];c=(l+1==a[i++])?c+1:1;if(c>m)m=c;}return m;}
``````

146 Characters (152 if the methods name must be `longest`)

``````    public static int longest(int[] array) {
Arrays.sort(array);

int max;
int i = 1;
int count = 1;
int last;
int size = array.length;

max = (size > 0) ? 1 : 0;

while (i < size) {
last = array[i - 1];
count = (last + 1 == array[i++]) ? count + 1 : 1;
if (count > max) max = count;
}

return max;
}
``````

## 125 Characters

``````public static int l(int[]a){int c=1,l=1,i=a.length;for(Arrays.sort(a);i>1;c=a[--i]-a[i-1]<2?c+1:1,l=c>l?c:l);return i>0?l:0;}
``````

``````public static int longest(int[] arr) {
int current = 1, longest = 1, i = a.length;
for (Arrays.sort(arr);
i > 1;
current = arr[--i] - arr[i - 1] < 2 ? current + 1 : 1, longest = current > longest ? current : longest)
;
return i > 0 ? longest : 0;
}
``````

124 Characters

``````public static int l(int[]a){int b=1,l=0,e=0,q;for(;b!=0+l;b++,l=e>l?e:l){q=e;for(int f:a)e=f==b?e+1:e;e=q==e?0:e;}return l;}
``````

``````public static int longest(int[] a) {
int n = 1, longest = 0, current = 0, tmp;
for (; n != 0 + longest; n++, longest = current > longest ? current : longest) {
tmp = current;
for (int f : a) current = f == n ? current + 1 : current;
current = tmp == current ? 0 : current;
}
return longest;
}
``````

Note that running this requires a bit of patience.

107 characters:

``````public static int l(int[]a){int i=0,j=0;for(Arrays.sort(a);j<a.length;)if(a[j]-a[i]!=j++-i)i++;return j-i;}
``````

``````public static int longest8(int[] a) {
Arrays.sort(a);
int i = 0, j = 0;

for (; j < a.length; j++) {

// start printing
for (int k : a)
System.out.printf("%4d", k);
System.out.println();
for (int k = 0; k < a.length; k++)
System.out.printf("%4s", k == i || k == j ? "^" : "");
System.out.println();
// end printing

if (a[j] - a[i] != j - i)
i++;
}

return j - i;
}
``````

It works much like kmecpp’s solution for the last contest.

After much thought, I realized that, [spoiler alert] after the array is sorted, to know whether a sequence of integers is consecutive, you only need to check the ends of the sequence. Iff a sequence is consecutive, the difference of the end elements equals the difference of the indices of the ends. For instance, the sequence 4, 5, 6, 7 is consecutive because the difference of the indices is 3 (first element has index 0, last has 3) and the difference of the ends is 7 - 4 = 3. Whereas 3, 5, 6, 7 is not because the difference of the indices is 3 and the difference of the ends is 7 - 3 = 4.

The method starts by checking this for the sequence between indices i=0 and j=0 inclusive. If the check passes, j is incremented so the next iteration the sequence to check is 1 longer. If the check fails, i and j are incremented together so the next iteration we check the next sequence of the same size (there’s no sense in checking sequences that are shorter than what has already passed because we’re looking for the longest sequence). The method will show what is going on on stdout.

## 104 Characters

``````public static int l(int[]a){int i=0,j=0;for(Arrays.sort(a);j<a.length;)i+=a[j]-a[j++-i]>i?0:1;return i;}
``````
``````public static int l(int[] a) {
int i = 0, j = 0;
for (Arrays.sort(a); j < a.length; )
i += a[j] - a[j++ - i] > i ? 0 : 1;
return i;
}
``````

This is based off of @eah’s submission, where the differences between two places in an array is compared to the differences in the index. My solution is different in that although `j` is still the index end of the length, `i` is the length instead of the start position.

144 characters:

``````public static int longest(int[]a){Arrays.sort(a);int m=0,i,j,l=a.length;for(i=0;i<l;i++)for(j=i;j<l&&a[j]-a[i]==j-i;j++)m=m>j=i?m:j-i;return m;}
``````

``````public static int longest(int[] a) {
Arrays.sort(a);
int m = 0, i, j, l = a.length;
for (i = 0; i < l; i++) {
for (j = i; j < l && a[j] - a[i] == j - i; j++) {
m = m > j - i ? m : j - i;
}
}
return m;
}
``````

Congratulations to @jus1in for once again winning the weekly programming contests, and also an honorable mention for @eah for coming up for the idea!

The next challenge will be posted shortly, be sure to watch the main thread for updates

Since my best solution is mostly just a shortening of @eah’s, they should receive an honorable mention.

Thanks for the reminder. Forgot to add that