How to find the pivot index in C++

The pivot index represents the position within an array where the cumulative sum of elements preceding it matches the cumulative sum of elements succeeding it. The specific value at the pivot index doesn’t affect this computation, and any array index can be the pivot index.

Here’s an illustration to understand the pivot index better.

#include <iostream>
using namespace std;
int main() {
  
  int arr[] = {1,4,6,8,8,5,5,10,13,9};  // Index 6 is the answer
  // Following for loop is for displaying the array.
  cout << "The array is : {";
  for (int i=0; i < sizeof(arr) / sizeof(int); i++){
    if (i+1 != sizeof(arr) / sizeof(int))
      cout << arr[i] << " , ";
    else
      cout << arr[i] << "}\n";
  }
  // Following loop calculates the total sum of the array.
  int sum = 0;
  for (int i=0; i < sizeof(arr) / sizeof(int) ; i++){
    sum = sum + arr[i];
  }
  // Following code finds the pivot index, if it exists.
  
  int total = 0;
  bool flag = true;
  for (int i=0; i < sizeof(arr) / sizeof(int); i++){
    sum = sum - arr[i];
    if (total == sum){
      flag = false;
      cout << "Index " << i << " is pivot" << endl;
    }
    total = total + arr[i];
  }
  // The following is displayed if no pivot index is found.
  if (flag){
    cout << "There is no pivot index" << endl;
  }
  return 0;
}

Explanation

Line 6: We initialize an array with the name arr with its pivot index commented out ahead.
Lines 9–15: We run a for loop for displaying the arr array.
Line 18: We initialize an integer variable sum as 0.
Lines 19–21: We run another for loop, which calculates the sum of all elements of the array and stores this value in sum.
Line 25: We initialize an integer variable total as 0. Later, we’ll iteratively add each element of the array in total and compare it with sum to find the pivot index.
Line 26: We initialize a boolean variable flag as true. We’ll use this variable to check whether the pivot index has been found. If the pivot index is found, we change the value of flag to false.
Lines 27–34: We run another for loop where i is initialized as 0, and goes up to the last index of the array. In each iteration of this loop, we first subtract the value of the element at the index number i from sum, and then compare that with the value of total. After the comparison, we add the value of this element to total.
- During the comparison, neither the variable sum, nor total contains the value of the element at the index i.
- During the comparison, sum is the sum of all elements at the indexes succeeding the index i, while total is the sum of all elements at the indexes preceeding the index i.
- When i is 0, the value of total is 0 while the value of sum is equal to the sum of all elements in the array, except the first one. When i is the last index of the array, the value of sum is 0, while total is equal to the sum of all elements in the array, except the last one.
- If, at any iteration, the comparison of sum and total proves them equal, flag becomes false and the loop stops.
Lines 37–39: If flag is still true, it means that sum and total never became equal in value i.e., no pivot index was found. In that case, a message (There is no pivot index) is displayed to the user stating that arr doesn’t contain a pivot index.

Knowledge test

In the following quiz, match the arrays given on the left side with their pivot indexes on the right side.

How to find the pivot index in C++

Code example

Explanation

Knowledge test

Conclusion: