Tìm vị trí cân bằng của mảng

Đề bài

Tìm các vị trí cân bằng của 1 array.

Vị trí cân bằng của array là chỉ số (index) mà tại đó tổng phần tử bên trái = tổng phần tử bên phải.

Example: A = [-7, 1, 5, 2, -4, 3, 0]

Tại index = 3:

• left_sum = -7 + 1 + 5 = -1
• right_sum = -4 + 3 + 0 = -1

Tại index = 6:

• left_sum = -7 + 1 + 5 + 2 + -4 + 3 = 0
• right_sum = 0 = 0;

Kết quả: index = 3, 6

Code

Suy nghĩ

Nhìn hình vẽ ta có thể thấy được: tổng array - total_sum = left_sum + array[i] + right_sum

• i là vị trí đang kiểm tra, có phải là vị trí cân bằng hay không ?

Giả sử ban đầu:

• left_sum = 0;
• right_sum = total_sum - left_sum - array[i] = total_sum - array[i]. (i là vị trí đang xét).

#include <stdio.h>
#include <stdint.h>

int sum_arr(int *array, int size)
{
    int sum = 0;
    for(int i = 0; i < size; i++)   
    {
        sum += array[i];
    }
    return sum;
}

void solve_the_problem(int *array, int size, int* result)
{
    int total_sum = sum_arr(array, size);   
    int left_sum  = 0;
    int right_sum = 0;

    for(int i = 0; i < size; i++)
    {
        right_sum = total_sum - left_sum - array[i];

        printf("Index %d: left_sum = %d, right_sum = %d\n", i, left_sum, right_sum);

        if(left_sum == right_sum)
        {
            printf("=> Equilibrium index at %d\n\n", i);
            (*result)++;
        }

        // cập nhật left_sum cho lần lặp tiếp theo
        left_sum += array[i];
    }
}

int main()
{
    int array[] = {-7, 1, 5, 2, -4, 3, 0};
    int size = sizeof(array) / sizeof(array[0]);
    int result = 0;

    solve_the_problem(array, size, &result);
  
    printf("Total equilibrium indices: %d\n", result);
  
    return 0;
}