Make k subarray sums equal

Array Math Greedy Sorting Number Theory

38.2% acceptance

Feb 25, 2026

522

You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element. You can do the following operation any number of times: Pick any element from arr and increase or decrease it by 1. Return the minimum number of operations such that the sum of each subarray of length k is equal. A subarray is a contiguous part of the array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn make_sub_k_sum_equal(arr: Vec<i32>, k: i32) -> i64 {
    let n = arr.len();
    let k = k as usize;

    fn gcd(a: usize, b: usize) -> usize {
      if b == 0 { a } else { gcd(b, a % b) }
    }

    let g = gcd(n, k);
    let mut visited = vec![false; n];
    let mut total: i64 = 0;

    for i in 0..g {
      if visited[i] {
        continue;
      }
      // Collect all elements in the orbit of i
      let mut group = Vec::new();
      let mut j = i;
      while !visited[j] {
        visited[j] = true;
        group.push(arr[j]);
        j = (j + k) % n;
      }
      // Find median and compute cost
      group.sort_unstable();
      let median = group[group.len() / 2];
      for &x in &group {
        total += (x - median).abs() as i64;
      }
    }
    total
  }
}