Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

3 sequential numbers

Name: eye 2012-04-04 16:06

Alright geniuses, if you think your programming ability is up to par, lets see you solve this:

Write an algorithm which in O(n) time finds 3 indices i, j, and k such that i < j < k and array[i] < array[j] < array[k].

Name: Anonymous 2012-04-04 17:16




$ cat sequarr.c                                                                                      
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define ARRFMT "a[%d]:%d\t"

int main(int argc, char** argv){
        int *arr, count;
        int i, j, k;

        count = argc - 1;
        arr = calloc(count, sizeof(int));
        for(i=0; i<count; ++i){
                arr[i] = strtol(argv[i+1], NULL, 10);
        }

        for(i=0; i<count; ++i){
                for(j=i; j<count; ++j){
                        for(k=j; k<count; ++k){
                                if( (arr[i] < arr[j]) &&
                                    (arr[j] < arr[k]) ){
                                        goto found;
                                }
                        }
                }
        }

        printf("None found!\n");
        return 0;

        found:
        printf(ARRFMT ARRFMT ARRFMT "\n",
                i, arr[i], j, arr[j], k, arr[k]);
        return 0;
}
$ ./sequarr 9 8 6 5 4 3 2 1
None found!
$ ./sequarr                
None found!
$ ./sequarr 2342 123 9999 3 444 8
None found!
$ ./sequarr 2342 123 9999 3 444 8 77
a[3]:3  a[5]:8  a[6]:77
$

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List