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

#1

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 ạ

This is a demo task.

An array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + … + A[P−1] = A[P+1] + … + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

int solution(int A[], int N);

that, given an array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

N is an integer within the range [0…100,000];
each element of array A is an integer within the range [−2,147,483,648…2,147,483,647].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

#2

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

1 Like
#3

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

#4

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].

1 Like
#5

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

#6

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]

3 Likes
#7

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

[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]

3 Likes
#8
Đã giải xong, ai muốn xem thì click vào dòng text này nha 
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<Integer> input = getFromArguments(args);
        List<Integer> indices = findEquilibriumIndices(input);

        System.out.print("Array: ");
        System.out.println(input);

        System.out.print("Indices: ");
        System.out.println(indices);
    }

    public static List<Integer> getFromArguments(String[] args) {
        List<Integer> numbers = new ArrayList<>(args.length);
        for (String number : args) {
            numbers.add(Integer.parseInt(number));
        }
        return numbers;
    }

    public static List<Integer> findEquilibriumIndices(List<Integer> numbers) {
        List<Integer> leftSum = getLeftSum(numbers);
        List<Integer> rightSum = getRightSum(numbers);

        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < leftSum.size(); i++) {
            if (leftSum.get(i).intValue() == rightSum.get(i).intValue()) {
                indices.add(i);
            }
        }

        return indices;
    }

    private static List<Integer> getLeftSum(List<Integer> numbers) {
        if (numbers.isEmpty()) {
            return new ArrayList<>();
        }

        List<Integer> sum = createList(numbers.size(), 0);
        for (int i = 1; i < sum.size(); i++) {
            sum.set(i, sum.get(i - 1) + numbers.get(i - 1));
        }

        return sum;
    }

    private static List<Integer> getRightSum(List<Integer> numbers) {
        if (numbers.isEmpty()) {
            return new ArrayList<>();
        }

        List<Integer> sum = createList(numbers.size(), 0);
        for (int i = sum.size() - 2; i >= 0; i--) {
            sum.set(i, sum.get(i + 1) + numbers.get(i + 1));
        }

        return sum;
    }

    private static <T> List<T> createList(int length, T initialNumber) {
        List<T> list = new ArrayList<T>(length);
        for (int i = 0; i < length; i++) {
            list.add(initialNumber);
        }
        return list;
    }
}

Input

java Main -1 3 -4 5 1 -6 2 1

Output

Array: [-1, 3, -4, 5, 1, -6, 2, 1]
Indices: [1, 3, 7]
2 Likes
#9

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

1 Like
#10

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;
}
#11

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 :slight_smile:

[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);
    }
}

}

2 Likes
#12

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

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.

2 Likes
#13

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 :blush:)

    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;
       
    }
#14

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

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

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?