Partition Array Equal Sum - C++ Solution

1. Introduction

In this blog post, we'll delve into a fascinating problem in array processing: partitioning an array into two contiguous subarrays such that both have the same sum. This problem is an excellent exercise in understanding array manipulation and cumulative sum concepts in C++.

Problem

The challenge is to take an integer array and divide it into two contiguous parts where the sum of elements in both parts is equal. We need to find and return the index that marks the start of the second subarray. If no such partition exists, we should return -1. Additionally, if multiple partitions are possible, we should return the index of the first occurrence.

Examples:

- Input: [6, -4, -3, 2, 3]

Output: 2

- Input: [6, -5, 2, -4, 1]

Output: -1

- Input: [1, -1, 1, -1, 1, -1]

Output: 0

2. Solution Steps

1. Calculate the total sum of the array.

2. Traverse the array while maintaining a cumulative sum.

3. Check if the cumulative sum equals half of the total sum at any point.

4. If such a point is found, return the current index as the start of the second subarray.

5. If the traversal is completed without finding such a point, return -1.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the partition index
int findPartitionIndex(vector<int>& nums) {
    int totalSum = 0, cumulativeSum = 0;

    // Calculate the total sum of the array
    for (int num : nums) {
        totalSum += num;
    }

    // Traverse the array
    for (int i = 0; i < nums.size(); ++i) {
        cumulativeSum += nums[i]; // Update the cumulative sum

        // Check if the current cumulative sum is half of the total sum
        if (cumulativeSum * 2 == totalSum) {
            return i + 1; // Partition index found
        }
    }

    return -1; // No partition found
}

int main() {
    vector<int> nums = {6, -4, -3, 2, 3};
    cout << "Partition Index: " << findPartitionIndex(nums) << endl;
    return 0;
}

Output:

Partition Index: 2

Explanation:

The findPartitionIndex function calculates the total sum of the input array. It then iterates over the array, maintaining a cumulative sum. If at any point, the cumulative sum is half of the total sum, it means the array can be partitioned into two subarrays with equal sums, and the function returns the next index as the start of the second subarray. If no such point is found, the function returns -1, indicating that no equal sum partition is possible.