In C++, find the index of the left pointer in an array after a possible move

In this question, we are given an array arr[] of size N. Our task is to find the index of the left pointer after possible moves in the array.

We have two pointers, one is the left pointer and the other is the right pointer.

The left pointer starts at index 0 and increases in value.

The right pointer starts from index (n-1) and the value decreases.

If the sum of the left pointers is less than the sum of the right pointers, the value of the pointer is increased, otherwise the value of the pointer is decreased. And the value of sum will be updated.

Let us understand this problem through an example,

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

Explanation The Chinese translation of −

is:

Explanation −

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.

Solution

Solve the problem by moving the left and right pointers according to the size of the sum. Then check if the left pointer is 1 greater than the right pointer.

Example

Program example illustrating how our solution works

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

Output

The index of left pointer after moving is 2

The above is the detailed content of In C++, find the index of the left pointer in an array after a possible move. For more information, please follow other related articles on the PHP Chinese website!