A slice function at codility

slice.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

#define ARRAY_SIZE 10000
#define MAX 100

int solution1(int A[], int N) {
  int total = 0;
  for (int i = 0; i < N; i++) {
    int tmp = 0;
    for (int j = i; j < N; j++) {
      tmp += A[j];
      if (tmp == 0) {
        total++;
      }   
    }   
  }
  return total;
}

int solution2(int A[], int N) {
  int total = 0;

  int* p = (int *)malloc(sizeof(int) * N); 
  for (int i = 0; i < N; i++) {
    p[i] = 0;
  }

  for (int i = 0; i < N; i++) {
    int tmp = 0;
    int last = i;
    if (p[i] > 0) {
      int k = i;
      while (p[k] > 0 && k < N) {
        total++;
        k = p[k];
      }   
      continue;
    }   
    for (int j = i; j < N; j++) {
      tmp += A[j];
      if (tmp == 0) {
        total++;
        if (0 < p[j + 1]) {
          int k = j + 1;
          while (p[k] > 0 && k < N) {
            total++;
            k = p[k];
          }   
          break;
        }   
        p[last] = j + 1;
        last = j + 1;
      }   
    }   
  }

  free(p);

  return total;
}

int main(int argc, const char* argv[]) {
  time_t t;
  srand((unsigned) time(&t));

  int* ns = malloc(sizeof(int) * ARRAY_SIZE);
  for (int i = 0; i < ARRAY_SIZE; i++) {
    ns[i] = (rand() % MAX * 2) - MAX;
  }

  double t1 = 0;
  double t2 = 0;
  int res1 = -1;
  int res2 = -1;
  int start = 0;
  for (int i = 0; i < 100; i++) {
    // Simple algorithm
    start = clock();
    res1 = solution1(ns, ARRAY_SIZE);
    t1 += (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;

    // Faster algorithm
    start = clock();
    res2 = solution2(ns, ARRAY_SIZE);
    t2 += (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;

    // Make sure the answer is the same
    assert(res1 == res2);
  }
  printf("solution1: (%.3fms)\n", t1 / 100);
  printf("solution2: (%.3fms)\n", t2 / 100);
  return 0;
}

The result.

solution1: (123.634ms)
solution2: (47.269ms)

The solution2 is much faster than the first one.