Given an array of random numbers, Push all the zero's of a given array to the end of the array. For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. The order of all other elements should be same. Expected time complexity is O(n) and extra space is O(1).

Makefile

push-zeros: push-zeros.c
	gcc -Wall -Werror -o push-zeros push-zeros.c

test: push-zeros
	./push-zeros

clean:
	rm -f push-zeros

.PHONY: test clean

push-zeros.c

#include <stddef.h>
#include <assert.h>

void push_zeros(int *in, size_t len) {
    int *reader = in;
    int *writer = in;

    // compact the array
    while (reader != in + len) {
        if (*reader == 0) {
            // if this is a zero, advance the reader but not the writer.
            reader += 1;
            continue;            
        } else {
            // otherwise, copy the number and advance both reader and writer.
            *writer = *reader;
            reader += 1;
            writer += 1;
        }
    }

    // fill the remaining space with zeros
    while (writer != in + len) {
        *writer = 0;
        writer += 1;
    }
}

void verify(int *expected, int *actual, size_t len) {
    int *a = expected;
    int *b = actual;
    while (a < expected + len && b < actual + len) {
        assert(*a == *b);
        a += 1;
        b += 1;
    }
}

void test0() {
    int input[] = {0, 1};
    int expected[] = {1, 0};
    size_t len = sizeof(input) / sizeof(int);
    push_zeros(input, len);
    verify(expected, input, len);
}

void test1() {
    int input[] = {1, 2, 0, 4, 3, 0, 5, 0};
    int expected[] = {1, 2, 4, 3, 5, 0, 0, 0};
    size_t len = sizeof(input) / sizeof(int);
    push_zeros(input, len);
    verify(expected, input, len);
}

void test2() {
    int input[] = {1, 2, 0, 4, 3, 0, 5, 0};
    int expected[] = {1, 2, 4, 3, 5, 0, 0, 0};
    size_t len = sizeof(input) / sizeof(int);
    push_zeros(input, len);
    verify(expected, input, len);
}

int main() {
    test0();
    test1();
    test2();    
    return 0;
}