Optimal Array Partition — Problem Statement & Solution Guide

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

int optimalPartition(vector<int>& weights) {
    int n = weights.size();
    if (n < 2) return 0; // Edge case, though problem states 1 <= i < n

    long long totalSum = 0;
    for (int w : weights) {
        totalSum += w;
    }

    long long leftSum = 0;
    long long minDiff = LLONG_MAX;
    int bestIndex = 1;

    for (int i = 1; i < n; i++) {
        leftSum += weights[i - 1];
        long long rightSum = totalSum - leftSum;
        long long diff = abs(leftSum - rightSum);

        if (diff < minDiff) {
            minDiff = diff;
            bestIndex = i;
        }
    }

    return bestIndex;
}

int main() {
    int n;
    cin >> n;
    vector<int> weights(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    cout << optimalPartition(weights) << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    /**
     * @param weights The input array of integers
     * @return The index i (1 <= i < n) that minimizes the absolute difference between the sum of weights[0..i-1] and weights[i..n-1].
     *         If multiple indices yield the same minimum difference, return the smallest such index.
     */
    public static int optimalPartition(int[] weights) {
        int n = weights.length;
        if (n < 2) return 0;

        long totalSum = 0;
        for (int w : weights) {
            totalSum += w;
        }

        long leftSum = 0;
        long minDiff = Long.MAX_VALUE;
        int bestIndex = 1;

        for (int i = 1; i < n; i++) {
            leftSum += weights[i - 1];
            long rightSum = totalSum - leftSum;
            long diff = Math.abs(leftSum - rightSum);

            if (diff < minDiff) {
                minDiff = diff;
                bestIndex = i;
            }
        }

        return bestIndex;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] parts = br.readLine().trim().split("\\s+");
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = Integer.parseInt(parts[i]);
        }
        System.out.println(optimalPartition(weights));
    }
}

def optimal_partition(weights):
    """
    Args:
        weights (list[int]): The input array of integers
    
    Returns:
        int: The index i (1 <= i < n) that minimizes the absolute difference between the sum of weights[0..i-1] and weights[i..n-1].
             If multiple indices yield the same minimum difference, return the smallest such index.
    """
    n = len(weights)
    if n < 2:
        return 0

    total_sum = sum(weights)
    left_sum = 0
    min_diff = float('inf')
    best_index = 1

    for i in range(1, n):
        left_sum += weights[i - 1]
        right_sum = total_sum - left_sum
        diff = abs(left_sum - right_sum)

        if diff < min_diff:
            min_diff = diff
            best_index = i

    return best_index

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    weights = list(map(int, data[1:n+1]))
    print(optimal_partition(weights))

/**
 * @param {number[]} weights - The input array of integers
 * @return {number} - The index i (1 <= i < n) that minimizes the absolute difference between the sum of weights[0..i-1] and weights[i..n-1].
 *                    If multiple indices yield the same minimum difference, return the smallest such index.
 */
function optimalPartition(weights) {
    const n = weights.length;
    if (n < 2) return 0;

    let totalSum = 0;
    for (let w of weights) {
        totalSum += w;
    }

    let leftSum = 0;
    let minDiff = Infinity;
    let bestIndex = 1;

    for (let i = 1; i < n; i++) {
        leftSum += weights[i - 1];
        const rightSum = totalSum - leftSum;
        const diff = Math.abs(leftSum - rightSum);

        if (diff < minDiff) {
            minDiff = diff;
            bestIndex = i;
        }
    }

    return bestIndex;
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    const n = parseInt(lines[0]);
    const weights = lines[1].split(' ').map(Number);
    console.log(optimalPartition(weights));
});