Đề 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;
}