Puzzle

Discussion in 'C Programming' started by Siddharth Taneja, Nov 6, 2004.

  1. Heres one I heard-

    For an array of integers in sorted order, which can have multiple
    occurences of any integer, form an array which lists the integers just
    once first, and then their duplicates in sorted order.

    Thus for

    1 1 1 2 2 3 9 9 9 10

    the o/p should be

    1 2 3 9 10 1 1 2 9 9

    The algorithm should be O(n) in running time...and should use only
    O(1) extra space.

    Siddharth Taneja
     
    Siddharth Taneja, Nov 6, 2004
    #1
    1. Advertisements

  2. Siddharth Taneja

    Ben Pfaff Guest

    The statement of the problem seems ambiguous about whether the
    output should be formed in-place or go to an external array. If
    it goes to an external array, it seems almost trivial: iterate
    through the input copying the first of each run, then iterate
    through the input again copying the rest of each run. It's not
    obvious to me that an in-place version is possible in O(n). Is
    it?

    Not really appropriate for comp.lang.c, so I've set followups
    appropriately.
     
    Ben Pfaff, Nov 6, 2004
    #2
    1. Advertisements

  3. This one seems to be more appropriate to comp.programming
    rather than c.l.c . So, setting the right follow-up hence.

    But anyway, here is the code ...


    /*****************************
    $Id$

    Created By: Karthik Kumar

    *****************************/
    #include <stdlib.h>
    #include <stdio.h>

    void reorder_array(int * in, size_t num, int * out);
    void print_array(int * a, size_t num);

    int main() {
    int out[10];
    int in[] = { 1 ,1 ,1 ,2 ,2, 3, 9, 9, 9 , 10 };
    reorder_array(in, 10, out);
    print_array(out, 10);
    return EXIT_SUCCESS;
    }

    void reorder_array(int * in, size_t num, int * out) {
    size_t i;
    size_t repetitions;
    int lastvisited;
    size_t nextneedle;
    size_t dupneedle;

    repetitions = 0;
    lastvisited = in[0];
    for (i = 1 ; i < num ; i++) {
    if ( in == lastvisited ) {
    repetitions++;
    }
    lastvisited = in;
    }
    /** Count the number of repetitions in the input array */

    lastvisited = in[0];
    nextneedle = 1; /* Normal Index */
    dupneedle = num - repetitions;
    /* Index where duplicate entries start */
    out[0] = in[0]; /* Copy the first element anyway */
    for (i = 1 ; i < num ; i++) {
    if ( in != lastvisited ) {
    out[nextneedle++] = in;
    } else {
    out[dupneedle++] = in;
    }
    lastvisited = in;
    }
    printf("\n Repetitions: %d\n", repetitions );
    }

    void print_array(int * a, size_t num) {
    size_t i ;
    for (i = 0 ; i < num ; i++) {
    printf("%d ", a);
    }
    printf("\n");
    }
     
    Karthik Kumar, Nov 6, 2004
    #3
  4. Siddharth Taneja

    CBFalconer Guest

    The answer seems simple, but it doesn't belong here. This would be
    quite welcome on comp.programming.
     
    CBFalconer, Nov 6, 2004
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.