Sum of elements of lower indices is equal to the sum of elements of higher indices

Em chưa hiểu đề lắm nên thắc mắc như sau: nếu trường hợp a(2) là cân bằng thì sẽ là a(0) +a(1) = a(3)+a(4)+a(5)+a(6)+a(7) có đúng ko ạ

Khi P = 2 là giá trị cân bằng thì a[0] + a[1] = a[3] + a[4] + … + a[7].

vậy bài này chi cần lấy left so sánh với right của phần tử đó thôi ạ? nếu bằng thì chỗ đó là cân bằng

Không đúng. Khi ta đã có tổng dãy sum thì dùng đại số sẽ có: [spoiler]2*acc_sum == sum - a[p][/spoiler].

acc_sum là cái gì vậy ạ, là sum/2 ạ?

lấy left so sánh với right

Về cơ bản là vậy, hiện mình chỉ nghĩ ra cách này thôi :

[details=Cách làm]Đặt một int left = 0, một int right = tổng các phần tử tử A[2] --> A[N - 1]
Rồi lại dùng 1 hàm for nữa chạy từ 2 --> N - 1, lúc đó

left += A[i - 1];
right -= A[i];

nếu left == right thì i chính là số cần tìm :)[/details]

Bạn cho lời giải vào spoil nhé

acc_sum là cái gì vậy ạ, là sum/2 ạ?

[spoiler]Cho i chạy từ 1 -> N thì acc_sum = a[1] + a[2] + … + a[i]. Ta có left + a[i+1] + right = sum […][/spoiler]

^
O(N^2) rồi này bạn whoops…

yeah, đó nó chấm điểm performance nữa anh ạ, O(N^2) hình như chỉ có 58 điểm thôi, còn dưới đây em có search trên mạng là 100 điểm, các huynh đệ tỉ mụi thích thì nghía ạ

int solution(int A[], int N) {
    long sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += (long) A[i];
    }
    long leftSum = 0;
    long rightSum = 0;

    for (int i = 0; i < A.length; i++) {
        rightSum = sum - (leftSum + A[i]);
        if (leftSum == rightSum) {
            return i;
        }
        leftSum += A[i];
    }
    return -1;
}

Na ná cách của mình :)) thử hộ mình xem cách này nó chấm bao nhiêu với

[details=Code]```
public static void find(int[] Input)
{
int right = 0, left = 0;
for(int i = 1; i < Input.length; i++)
{
right += Input[i];
}

for(int i = 1; i < Input.length; i++)
{
    left += Input[i - 1];
    right -= Input[i];
    if(left == right)
    {
        System.out.println(i);
    }
}

}

Code của mình O(n) mà

Link bài giải nè, có 100% JavaScript, C#, Java (giống như cái bạn copy). Kéo xuống dưới có comment về dynamic programming của Hilary Brobbey, ý tưởng code của ổng giống ý tưởng của mình.

A zero-indexed array given & An equilibrium index of this array

Thuật toán trên mình thấy đang linear Sum cho array.

   static int linearSum(int A[]){
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
        }
        return sum;
    }

Liệu cách sum này có được gọi là < O(N) ? (Nó ngẻo ở vấn đề memory )

    static int binarSum(int[] nums, int start, int end){

        int dif = end - start;  
             
        if(dif > 1) {
            int pivot = (int) ((start + end)/2);
            int[] subs = {binarSum(nums, start, pivot), binarSum(nums, pivot+1, end)};               
            return binarSum(subs, 0, 1);
        }
        else if(dif == 1)      
            return (nums[start] + nums[end]);
        else if(dif == 0)
            return nums[start];
        return 0;
       
    }

T(n) = 2T(n/2) + O(1) = O(n) mem cũng O(n) luôn, nhưng là stack nên chết sình

Lí do thì giống như đá World Cup vậy thôi.