Solutions for https://codility.com/public-report-detail/

first.c

#include "stdio.h"

// Best solution. Complexity: 2N
int solution(int A[], int N) {
    if (N == 0) return -1;
    if (N == 1) return 0;
    int equilibriumIdx = -1;

    // Compute sum or array except first element
    int rightSum = 0;
    for (int i = 1; i < N; ++i)
    {
        rightSum += A[i];
    }
    if (rightSum == 0) {
        // We're lucky
        equilibriumIdx = 0;
    }

    int leftSum = 0;
    for (int i = 1; i < N; ++i)
    {
        leftSum += A[i - 1];
        rightSum -= A[i];
        printf("For %d: %d vs %d\n", i, leftSum, rightSum);
        if (leftSum == rightSum) {
            // TODO: return
            printf("Valid %d\n", i);
            equilibriumIdx = i;
        }
    }
    return equilibriumIdx;
}

int main(int argc, char const *argv[])
{
    //int arr[] = {1, 3, 5, 4, 0, 0, 0, 0}; // Solution: 2
    int arr[] = {-1, 3, -4, 5, 1, -6, 2, 1}; // Solutions: 1, 3 & 7
    int size = sizeof(arr) / sizeof(int);
    printf("equilibriumIdx=%d\n", solution(arr, size));
    return 0;
}

// Previous versions

// Like bubble sort :3. Complexity: N2
int firstSolution(int A[], int N) {
    if (N == 0) return -1;

    int leftSum, rightSum;
    int equilibriumIdx = -1;
    for (int i = 0; i < N; ++i)
    {
        leftSum = rightSum = 0;
        for (int j = 0; j < N; ++j)
        {
            if (j < i) {
                leftSum += A[j];
            } else if (j > i) {
                rightSum += A[j];
            }
        }
        printf("For %d: %d vs %d\n", i, leftSum, rightSum);
        if (leftSum == rightSum) {
            // TODO: return
            printf("Valid %d\n", i);
            equilibriumIdx = i;
        }
    }
    return equilibriumIdx;
}

// Complexity 2N but not the best
int solutionMaybe(int A[], int N) {
    if (N == 0) return -1;
    int equilibriumIdx = -1;

    // Look for easiest solution
    int leftIdx = 0, rightIdx = N - 1;
    int leftSum = 0, rightSum = 0;
    while (leftIdx != rightIdx) {
        printf("1) A[%d:]=%d & A[:%d]=%d\n", leftIdx, leftSum, rightIdx, rightSum);

        if (leftSum <= rightSum) {
            leftSum += A[leftIdx];
            leftIdx++;
        } else {
            rightSum += A[rightIdx];
            rightIdx--;
        }
    }
    if (leftSum == rightSum) {
        printf("We're lucky\n");
        return leftIdx;
    }

    // Not found, we have to use already compute counts in order to find another solution
    printf("Not found for A[%d:]=%d & A[:%d]=%d\n", leftIdx, leftSum, rightIdx, rightSum);
    int newLeftSum = leftSum, newRightSumForLeft = rightSum;
    int newLeftSumForRight = leftSum, newRightSum = rightSum;
    while (leftIdx > 0 || rightIdx < N - 1) {
        printf("2) %d / %d\n", leftIdx, rightIdx);
        if (leftIdx > 0) {
            leftIdx--;
            newLeftSum = newLeftSum - A[leftIdx];
            newRightSumForLeft = newRightSumForLeft + A[leftIdx + 1];

            printf("%d vs %d for leftIdx=%d\n", newLeftSum, newRightSumForLeft, leftIdx);
            if (newLeftSum == newRightSumForLeft) {
                // TODO: return
                printf("FOUND for left=%d == %d\n", leftIdx, newLeftSum);
                equilibriumIdx = leftIdx;
            }
        }

        if (rightIdx < N - 1) {
            rightIdx++;
            newRightSum = newRightSum - A[rightIdx];
            newLeftSumForRight = newLeftSumForRight + A[rightIdx - 1];

            printf("%d vs %d for rightIdx=%d\n", newRightSum, newLeftSumForRight, rightIdx);
            if (newRightSum == newLeftSumForRight) {
                // TODO: return
                printf("FOUND for right=%d == %d\n", rightIdx, newRightSum);
                equilibriumIdx = rightIdx;
            }
        }
    }

    return equilibriumIdx;
}