# Puzzle

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

1. ### Siddharth TanejaGuest

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

2. ### Ben PfaffGuest

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

3. ### Karthik KumarGuest

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
4. ### CBFalconerGuest

The answer seems simple, but it doesn't belong here. This would be
quite welcome on comp.programming.

CBFalconer, Nov 6, 2004