Tìm chỉ số con trỏ trái sau di chuyển trong mảng C++

Cho mảng arr[] kích thước N. Hai con trỏ: left (bắt đầu 0, tăng) và right (bắt đầu n-1, giảm). Con trỏ nào có tổng nhỏ hơn sẽ di chuyển. Nhiệm vụ: tìm chỉ số cuối cùng của con trỏ trái.

Ví dụ minh họa

Input: arr[] = {5, 6, 3, 7, 9, 4} Output: 2

Quá trình: left=0(sum=5), right=5(sum=4) → right--; left=0(5), right=4(13) → left++; left=1(11), right=4(13) → left++; left=2(14), right=4(13) → right--; left=2(14), right=3(20) → dừng. Left=2.

Phương pháp giải

Mô phỏng quá trình: cập nhật tổng và di chuyển con trỏ có tổng nhỏ hơn cho đến khi left >= right - 1.

Ví dụ chương trình

#include <iostream> 
using namespace std; 

int findIndexLeftPointer(int arr[], int n) {
    if (n == 1) return 0;
    int leftPointer = 0, rightPointer = n - 1;
    int leftSum = arr[0], rightSum = arr[n - 1];
    while (rightPointer > leftPointer + 1) {
        if (leftSum < rightSum) {
            leftPointer++;
            leftSum += arr[leftPointer];
        } else if (leftSum > rightSum) {
            rightPointer--;
            rightSum += arr[rightPointer];
        } else break;
    }
    return leftPointer;
}

int main() {
    int arr[] = {5, 6, 3, 7, 9, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Chỉ số con trỏ trái cuối cùng: " << findIndexLeftPointer(arr, n);
    return 0;
}

Kết quả

Chỉ số con trỏ trái cuối cùng: 2