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.
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 belongest)
A more readable version:
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;
}
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;}
Readable version:
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;
}
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;}
Readable version:
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.
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;}
Readable:
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.
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.
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;}
Readable version:
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;
}
