Array Division Solution with Explanation | CSES Problem Set | Binary Search

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.

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector<int>

bool helper(vi &v, int mid, int k)
{
    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] > mid)
            return false;
        sum += v[i];
        if (sum > mid)
        {
            cnt++;
            sum = v[i];
        }
    }
    cnt++;
    return cnt <= k;
}

void solve()
{

    int n, k;
    cin >> n >> k;

    vi v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    int ans = 0;
    int low = *max_element(v.begin(), v.end()), high = accumulate(v.begin(), v.end(), 0LL), mid;

    while (high >= low)
    {
        mid = (high + low) / 2;
        if (helper(v, mid, k))
        {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }

    cout << ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    clock_t z = clock();

    int t = 1;
    //   cin >> t;
    while (t--)
        solve();

    return 0;
}

Let’s break down the major code components:

helper(v, mid, k) – determines whether the array can be divided into ≤ k subarrays without any subarray sum exceeding mid.
Inside the loop, elements are accumulated into sum. If adding another element exceeds mid, a new subarray starts and the count cnt increases.
The condition cnt <= k indicates feasibility.

The main function then performs binary search:

low = max(v)
high = sum(v)
while low ≤ high:
    mid = (low + high) / 2
    if helper(mid) is true:
        ans = mid
        high = mid - 1
    else:
        low = mid + 1

The final ans will be the smallest possible value of the maximum subarray sum achievable by dividing the array into k parts.

Example walkthrough:
For input [2,4,7,3,5] with k = 3: - Start with low = 7 (largest element) and high = 21 (total sum). - Through binary search, we find that mid = 8 allows splitting into ≤ 3 parts: [2,4], [7], [3,5]. - Hence, the optimal maximum sum is 8.

Tagscsesarray division solution csesarray division csesarray division

Raunit Verma

Technical Writer at CodingKaro

Share this on

Array Division Solution with Explanation | CSES Problem Set | Binary Search

Raunit Verma

CodingKaro App