C++의 배열에서 가능한 이동 후 왼쪽 포인터의 인덱스 찾기

이 문제에서는 크기가 N인 배열 arr[]이 제공됩니다. 우리의 임무는 배열에서 가능한 이동 후 왼쪽 포인터의 인덱스를 찾는 것입니다. .

배열에 대한 두 개의 포인터가 있습니다. 하나는 왼쪽 포인터이고 다른 하나는 오른쪽 포인터입니다.

왼쪽 포인터는 인덱스 0에서 시작하고 값이 증가합니다.

오른쪽 포인터는 인덱스(n-1)에서 시작하여 값이 감소합니다.

순회한 합이 다른 것보다 작으면 포인터 값이 증가합니다. 즉, 왼쪽 포인터의 합이 오른쪽 포인터의 합보다 작으면 왼쪽 포인터가 증가하고 그렇지 않으면 오른쪽 포인터가 감소합니다. 그리고 합계가 업데이트됩니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

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

설명 -

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.

솔루션 접근 방식

문제에 대한 간단한 해결책은 합을 기준으로 leftPointer와 rightPointer를 이동하는 것입니다. 그런 다음 leftPointer가 rightPointer보다 하나 큰지 확인합니다.

예시

솔루션 작동을 설명하는 프로그램

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

출력

The index of left pointer after moving is 2