“Find a Partition Point Where Two Parts Have Almost Equal Sum in an Array (C Program)”
C
Medium
2 views
Problem Description
The array needs to be divided into two equal parts such that the sums of both parts are almost equal - what would be the strategy to find the partition point?
Official Solution
#include <stdio.h>
#include <stdlib.h> // for abs()
int main() {
int arr[] = {10, 20, 30, 40, 50};
int size = sizeof(arr) / sizeof(arr[0]);
int totalSum = 0;
for (int i = 0; i < size; i++) {
totalSum += arr[i];
}
int leftSum = 0;
int rightSum = 0;
int minDiff = totalSum;
int partitionIndex = -1;
// Find partition point
for (int i = 0; i < size - 1; i++) {
leftSum += arr[i];
rightSum = totalSum - leftSum;
int diff = abs(leftSum - rightSum);
if (diff < minDiff) {
minDiff = diff;
partitionIndex = i;
}
}
printf("Partition point is after index %dn", partitionIndex);
printf("Left part sum = %dn", leftSum);
printf("Right part sum = %dn", totalSum - leftSum);
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!