Làm toán giải trí một tí nhỉ?

Ok, chào tất cả anh em

Chả là cuối tuần, ở nhà rảnh rang, trời thì se se lạnh, mũi hơi tắc, chỉ muốn co ro quấn chăn ôm laptop cho ấm. Lang thang thi cái cuộc thi lập trình của bọn Top Career gì đó :v vô tình vấp phải 1 bài test demo, mà mình thấy khá hay, nên muốn chia sẻ lên đây cho cả nhà

Đề bài:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
A zero-indexed 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:
 
function solution($A);
 
that, given a zero-indexed 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), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Dịch đại khái là:

1
2
3
4
5
6
7
8
Ta có 1 indexed array A gồm N phần tử là các số tự nhiên bất kỳ. Tìm chỉ số cân bằng P sao cho P là
 
 - Key của array A
 - Thỏa mãn điều kiện: A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
 - P = 0 hoặc P= N-1 đều có thể là giá trị đúng
 - Có thể có nhiều hoặc 1 giá trị P
 - Nếu không có giá trị nào, function cần return -1
Các điều kiện về complexity, assumption mời xem phần tiếng Anh nhé, lười dịch :D

Rồi, đề bài là như vậy, yêu cầu viết 1 function dưới ngôn ngữ nào cũng được, thời gian làm bài là 30 phút.

GIẢI

(Đây là cách giải của mình, ai có cách nào hay hơn thì comment nhé )

Hướng giải của mình là sẽ chia mảng 1 chiều này thành 2 phần, Tổng Trái và Tổng Phải. Sau đó chạy dần từ trái qua phải của mảng và so sánh 2 tổng này với nhau. EZPZ phải không? :))

Mình code PHP nhé, đầu tiên gán giá trị default phát (thói quen thôi, PHP không cần initialize biến)

PHP
1
2
3
4
5
6
7
8
9
function ($A)
{
    $sumLeft = 0;
    $sumRight = array_sum($A);
    $equi = -1;
}
 
//$A là arrray nhập vào
//$equi là số P cần tìm

Rồi, bây giờ lặp qua cái array A xem sao nhỉ?

1
2
3
4
5
6
7
8
9
10
11
12
function ($A)
{
    $sumLeft = 0;
    $sumRight = array_sum($A);
    $equi = -1;
 
    for ($index = 0; $index < count($A); $index++) {
        //So sánh $sumLeft với $sumRight trong này
        //Mình dùng for thay vì foreach do lý do performance
    }
    return $equi;
}

Bắt đầu so sánh, và phải trừ dần $sumRight tăng dần $sumLeft với giá trị của mỗi element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function ($A)
{
    $sumLeft = 0;
    $sumRight = array_sum($A);
    $equi = -1;
 
    for ($index = 0; $index < count($A); $index++) {
        $tempRight = $sumRight - $A[$index];
        if ($sumLeft === $tempRight) {
            $equi = $index;
            return $equi;
        } else {
            $sumLeft += $A[$index];
            $sumRight = $tempRight;
        }
    }
    return $equi;
}

Trông có vẻ ổn ổn rồi đấy nhỉ :))

Nhưng thực ra là đếch ổn, mình còn chưa check null cơ mà =)) cái cơ bản nhất còn suốt ngày quên đây

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function ($A)
{
    $sumLeft = 0;
    $sumRight = array_sum($A);
    $equi = -1;
 
    if (count($A)) {
        for ($index = 0; $index < count($A); $index++) {
            $tempRight = $sumRight - $A[$index];
            if ($sumLeft === $tempRight) {
                $equi = $index;
                return $equi;
            } else {
                $sumLeft += $A[$index];
                $sumRight = $tempRight;
            }
        }
        return $equi;
    }
    return -1;
}

Ok done! Nào, bây giờ test thôi!

PHP
1
echo demo([4, 35, 80, 123, 12345, 44, 8, 5, 24, 3]);

Chuẩn đét :)) Test thử với dữ liệu khác xem sao

PHP
1
echo demo([-1, 3, -4, 5, 1, -6, 2, 1]);

Done!

Hy vọng anh em giải toán vui vẻ :)) có solution nào ngon hơn nhớ comment -_- đừng có ém hàng

in Tech

Lại nói về chuyện nền kinh tế mới: Attention Economy

Về chúng tôi:

Follow us