Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước N. Nhiệm vụ của chúng ta là tìm chỉ mục của con trỏ bên trái sau khi có thể di chuyển trong mảng .
Chúng tôi có hai con trỏ cho mảng, một con trỏ bên trái và một con trỏ bên phải.
Con trỏ trái bắt đầu ở chỉ mục 0 và giá trị được tăng dần.
Con trỏ bên phải bắt đầu từ chỉ mục (n-1) và giá trị đang giảm dần.
Giá trị của một con trỏ tăng lên nếu tổng được duyệt nhỏ hơn giá trị khác, tức là nếu tổng của con trỏ trái nhỏ hơn tổng của con trỏ phải, thì con trỏ trái được tăng lên nếu không thì con trỏ phải bị giảm. Và tổng được cập nhật.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2 Giải thích -
leftPointer = 0 -> sum = 5, rightPointer = 5 -> sum = 4. Move rightPointer leftPointer = 0 -> sum = 5, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 1 -> sum = 11, rightPointer = 4 -> sum = 13. Move leftPointer leftPointer = 2 -> sum = 14, rightPointer = 4 -> sum = 13. Move rightPointer leftPointer = 2 -> sum = 14, rightPointer = 3 -> sum = 20. Move rightPointer Position of the left pointer is 2.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là di chuyển LeftPointer và rightPointer dựa trên tổng. Và sau đó kiểm tra xem leftPointer có lớn hơn rightPointer không.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
if(n == 1)
return 0;
int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
while (rightPointer > leftPointer + 1) {
if (leftPointerSum < rightPointerSum) {
leftPointer++;
leftPointerSum += arr[leftPointer];
}
else if (leftPointerSum > rightPointerSum) {
rightPointer--;
rightPointerSum += arr[rightPointer];
}
else {
break;
}
}
return leftPointer;
}
int main() {
int arr[] = { 5, 6, 3, 7, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
return 0;
} Đầu ra
The index of left pointer after moving is 2