title: Intuition behind getting distance from the end of vector versus just counting
body: <p>I am trying to solve a <a href="https://www.geeksforgeeks.org/count-the-number-of-ways-to-divide-an-array-into-three-contiguous-parts-having-equal-sum/" rel="nofollow noreferrer">GeeksForGeeks question</a> as below:</p>
  <p>Count the number of ways to divide an array into three contiguous parts having equal sum: Given an array of <code>n</code> numbers, find the <em>number of</em> index pairs <code>i</code> and <code>j</code> such that sum of elements from <code>0</code> to <code>i-1</code> is equal to the sum of elements from <code>i</code> to <code>j</code> is equal to the sum of elements from <code>j+1</code> to <code>n-1</code>.  For the input <code>{1, 2, 3, 0, 3}</code>, the output is <code>2</code> (We have indices: (0, 1), (2, 2) and (3, 4) and (0, 1), (2, 3) and (4, 4))</p>
  <p>Here's the code:</p>
  <pre class="lang-cpp prettyprint-override"><code>// C++ program to count number of ways we can 
  // partition an array in three parts with equal 
  // sum. 
  #include&lt;bits/stdc++.h&gt; 
  using namespace std; 
  
  // binary search to find the number of required 
  // indices in suffix array. Returns index of 
  // first element which is greater than x. 
  int binarysearch(vector &lt;int&gt; &amp;v, int x) 
  { 
      int low = 0, high = v.size()-1; 
      while (low &lt;= high) 
      { 
          int mid = (low + high)/2; 
          if (v[mid] &lt;= x) 
              low = mid + 1; 
          else if (v[mid] &gt; x &amp;&amp; v[mid-1] &lt;= x) 
              return mid; 
          else if (v[mid] &gt; x &amp;&amp; mid == 0) 
              return mid; 
          else
              high = mid-1; 
      } 
      return -1; 
  } 
  
  // function to calculate the number of ways to 
  // divide the array into three contiguous parts 
  int CountContiguousParts(int arr[] ,int n) 
  { 
      int count = 0; // initializing answer 
  
      // Creating and filling prefix array 
      int prefix[n]; 
      prefix[0] = arr[0]; 
      for (int i=1; i&lt;n; i++) 
          prefix[i] = prefix[i-1] + arr[i]; 
  
      // Total sum of elements is equal to last 
      // value in prefix array. 
      int total_sum = prefix[n-1]; 
  
      // If sum of all the elements is not divisible 
      // by 3, we can't divide array in 3 parts of 
      // same sum. 
      if (total_sum%3 != 0) 
          return 0; 
  
      // Creating and filling suffix array 
      int suffix[n]; 
      suffix[n-1] = arr[n-1]; 
      for (int i=n-2; i&gt;=0; i--) 
          suffix[i] = suffix[i+1] + arr[i]; 
  
      //&lt;------Don't understand why we are doing things below-------------&gt;
      // Storing all indexes with suffix 
      // sum equal to total sum by 3. 
      vector &lt;int&gt; v; 
      for (int i=0; i&lt;n; i++) 
          if (suffix[i] == total_sum/3) 
              v.push_back(i); 
  
      // Traversing the prefix array and 
      // doing binary search in above vector 
      for (int i=0; i&lt;n; i++) 
      { 
          // We found a prefix with total_sum/3 
          if (prefix[i] == total_sum/3) 
          { 
              // Find first index in v[] which 
              // is greater than i+1. 
              int res = binarysearch(v, i+1); 
  
              if (res != -1) 
                  count += v.size() - res; 
          } 
      } 
  
      return count; 
  } 
  
  // driver function 
  int main() 
  { 
      int arr[] = {1 , 2 , 3 , 0 , 3}; 
      int n = sizeof(arr)/sizeof(arr[0]); 
      cout &lt;&lt; CountContiguousParts(arr, n); 
      return 0; 
  } 
  
  </code></pre>
  <p>I do not follow the logic behind creating a vector <code>v</code> storing all indexes with suffix sum equal to (<code>total sum/3</code>) and then doing a binary search that returns index of first element which is greater than <code>i+1</code>.</p>
  <p>For the given example <code>{1, 2, 3, 0, 3}</code>, the prefix array is <code>{1, 3, 6, 6, 9}</code>, while the suffix array is <code>{9, 8, 6, 3, 3}</code>.  So as per the above logic, for the <code>3</code> at index i=1 in the prefix array, we find <code>3</code> at index i=3 in the suffix array and add <code>v.size() - res</code> to <code>count</code>, which is our answer <code>2</code> here.  <strong>However, I don't understand what this does and how it gives us our answer.</strong></p>
  <p>What <em>I</em> was thinking instead is for the the <code>3</code> at index i=1 in the prefix array, we should count the number of occurrences of <code>3</code> starting <code>i+1</code> in the suffix array and return that count.</p>
  <p>Could someone please elaborate what the above code is tryna do?</p>