Array Division

You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

Example:

Input:  n = 5, k = 3, arr = {2, 4, 7, 3, 5}
Output: 8

Approach

Java

public class ArrayDivision {
    public static void main(String[] args) {

        long n = 5, k = 3;
        long[] arr = { 2, 4, 7, 3, 5 };

        System.out.println(arrayDivision(n, k, arr));

    }

    static boolean check(long mid, long n, long k, long[] arr) {
        long cnt = 1, cur = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] > mid) {
                return false;
            } else if (cur + arr[i] > mid) {
                cur = arr[i];
                cnt++;
            } else {
                cur += arr[i];
            }
        }
        if (cnt <= k)
            return true;
        return false;
    }

    static long arrayDivision(long n, long k, long[] arr) {

        long lo = 1, hi = (long) 1e18;
        while (lo + 1 < hi) {
            long mid = (lo + hi) / 2;
            if (check(mid, n, k, arr))
                hi = mid;
            else
                lo = mid;
        }
        return hi;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

bool check(long long mid, long long n,
           long long k, vector<long long> &arr)
{
    long long cnt = 1, cur = 0;
    for (long long i = 0; i < n; i++)
    {
        if (arr[i] > mid)
        {
            return false;
        }
        else if (cur + arr[i] > mid)
        {
            cur = arr[i];
            cnt++;
        }
        else
        {
            cur += arr[i];
        }
    }
    if (cnt <= k)
        return true;
    return false;
}

long long arrayDivision(long long n, long long k,
                        vector<long long> &arr)
{

    long long lo = 1, hi = 1e18;
    while (lo + 1 < hi)
    {
        long long mid = (lo + hi) / 2;
        if (check(mid, n, k, arr))
            hi = mid;
        else
            lo = mid;
    }
    return hi;
}

int main()
{
    long long n = 5, k = 3;
    vector<long long> arr = {2, 4, 7, 3, 5};

    cout << arrayDivision(n, k, arr) << "\n";

    return 0;
}