Problem Explanation

Suppose you are given an array of integers and your task is to find out whether or not this array can be partitioned into three non-empty parts so that the sum of elements in each part is the same.

Let's understand this query through an example: Suppose you are given an array: [0,2,1,-6,6,-7,9,1,2,0,1]. In this case, you can divide the array into three non-empty parts [0,2,1], [-6,6,-7,9,1] and [2,0,1] where the sum of elements in each of the parts is equal to 3. So, the function should return true.

On the other hand, if you have an array [0,2,1,-6,6,7,9,-1,2,0,1], no matter how you divide it, the sum of elements in each of the three parts will not be equal. So, the function should return false.

Approach Explanation

The approach to solving this problem is to calculate the total sum of all elements in the array first. If it is not a multiple of 3, we cannot divide it into 3 parts with equal sums, hence return false.

If total sum is a multiple of 3, we divide it by 3 to get the sum of each part.

We then iterate over the array and keep a running total of elements. As soon as the running total equals the required sum, we increment a counter (since we've found one partition with the required sum) and reset the running total. We repeat this till we've found at least three partitions with the required sum.

Please note: Array with all elements 0 is an edge case. Since the sum of all elements is 0, which is divisible by 3, it will return true. But it can be partitioned into more than 3 parts with equal sum (0). Our function handles this case too.

Python Solution

1
2python
3from typing import List
4
5class Solution:
6    def canThreePartsEqualSum(self, arr: List[int]) -> bool:
7        total_sum = sum(arr)
8        if total_sum % 3 != 0:
9            return False
10
11        target_sum = total_sum // 3
12        current_sum = 0
13        partition_count = 0
14
15        for num in arr:
16            current_sum += num
17            if current_sum == target_sum:
18                partition_count += 1
19                current_sum = 0
20
21        return partition_count >= 3

Java Solution:

1
2java
3class Solution {
4    public boolean canThreePartsEqualSum(int[] arr) {
5        int totalSum = 0;
6        for (int num : arr) {
7            totalSum += num;
8        }
9        if (totalSum % 3 != 0) {
10            return false;
11        }
12
13        int targetSum = totalSum / 3;
14        int currentSum = 0;
15        int partitionCount = 0;
16
17        for (int num : arr) {
18            currentSum += num;
19            if (currentSum == targetSum) {
20                partitionCount++;
21                currentSum = 0;
22            }
23        }
24        return partitionCount >= 3;
25    }
26}

JavaScript Solution:

1
2javascript
3class Solution {
4    canThreePartsEqualSum(arr) {
5        let totalSum = arr.reduce((a, b) => a + b, 0);
6        if (totalSum % 3 !== 0) {
7            return false;
8        }
9
10        let targetSum = totalSum / 3;
11        let currentSum = 0;
12        let partitionCount = 0;
13
14        for (let num of arr) {
15            currentSum += num;
16            if (currentSum === targetSum) {
17                partitionCount++;
18                currentSum = 0;
19            }
20        }
21        return partitionCount >= 3;
22    }
23}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    bool canThreePartsEqualSum(vector<int>& arr) {
6        int totalSum = accumulate(arr.begin(), arr.end(), 0);
7        if (totalSum % 3 != 0) {
8            return false;
9        }
10
11        int targetSum = totalSum / 3;
12        int currentSum = 0;
13        int partitionCount = 0;
14
15        for (int num : arr) {
16            currentSum += num;
17            if (currentSum == targetSum) {
18                partitionCount++;
19                currentSum = 0;
20            }
21        }
22        return partitionCount >= 3;
23    }
24};

C# Solution:

1
2csharp
3public class Solution {
4    public bool CanThreePartsEqualSum(int[] arr) {
5        int totalSum = arr.Sum();
6        if (totalSum % 3 != 0) {
7            return false;
8        }
9
10        int targetSum = totalSum / 3;
11        int currentSum = 0;
12        int partitionCount = 0;
13
14        foreach (int num in arr) {
15            currentSum += num;
16            if (currentSum == targetSum) {
17                partitionCount++;
18                currentSum = 0;
19            }
20        }
21        return partitionCount >= 3;
22    }
23}

The array is traversed in each algorithmic solution in order to sum its contents as a whole. A conditional statement is then used to examine whether the total_sum can be evenly divided into three parts or not. This is because an array that cannot be evenly split into three parts cannot meet the problem requirements.

If total_sum is divisible by three, we establish a new 'partition_count' variable, which keeps track of how many portions of the array equal the target_sum. As we iterate through the array once more, we sum the elements part by part and check if this running partial sum equals our target_sum. As soon as it does, indicating that a portion with the expected total has been discovered, we increment the partition_count and reset the sum.

While looping through numbers, if we discover three or more partitions with equal sums, we can conclude that it is possible to split the array into three parts with equal sums and return true. It's important to notice that we want to find at least three parts. It is possible, for example, to split the array [1,-1,1,-1,1,-1] into six parts, but it still meets our conditions.

Each solution follows the same logic but programmed in different programming languages: Python, Java, JavaScript, C++, and C#. The fundamental concepts of loops, conditionals, and array operations are applied in each of them. Thus, it can be a great advantage for developers or enthusiasts who want to learn different programming languages or prepare for interview exams by practicing a single algorithmic problem in various languages.

This also helps in understanding how different programming languages scale on a single problem and how different languages handle memory, CPU usage and execution time in representing the same problem. These insights can be useful to analyze and update algorithms by applying different techniques and syntax for better optimization.