We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make K-Subarray Sums Equal

Number: 2670

Difficulty: Medium

Paid? No

Companies: Amazon, observe.ai

Problem Description

Given a circular integer array arr and an integer k, you can increase or decrease any element by 1 per operation. The goal is to ensure that the sum of every contiguous subarray of length k is equal. Return the minimum number of operations required to achieve this condition.

Key Insights

  • The condition that every contiguous subarray of length k has the same sum forces arr[i] = arr[(i+k) mod n] for every index i.
  • This observation partitions the indices into several cycles. Each cycle is formed by starting from an index and repeatedly adding k modulo n.
  • The number of cycles equals d = gcd(n, k).
  • To satisfy the condition, all elements within a cycle need to be equal.
  • Minimizing the total number of operations to make all numbers equal in a cycle is equivalent to aligning them to their median.
  • The overall answer is the sum of operations over all cycles.

Space and Time Complexity

Time Complexity: O(n log(n/d)) in the worst case (typically O(n log n) since sorting is done on each cycle).
Space Complexity: O(n) for storing cycle elements.

Solution

The solution involves first determining the number of cycles by computing the greatest common divisor (gcd) of n (the array length) and k. For each cycle:

  1. Collect the elements following the cycle pattern.
  2. Sort the cycle and choose the median value as the optimal target since aligning numbers to their median minimizes the sum of absolute differences.
  3. Sum the absolute differences for all elements in the cycle. Finally, add the results for all cycles, which gives the minimal number of operations required.

Code Solutions

import math

def minOperations(arr, k):
    n = len(arr)
    d = math.gcd(n, k)  # number of cycles
    total_operations = 0
    
    for i in range(d):
        cycle = []
        j = i
        # Traverse and collect the cycle's elements
        while True:
            cycle.append(arr[j])
            j = (j + k) % n
            if j == i:
                break
        
        # Sort cycle and choose median as target
        cycle.sort()
        m = len(cycle)
        median = cycle[m // 2]
        
        # Sum absolute differences with the median
        for value in cycle:
            total_operations += abs(value - median)
    
    return total_operations

# Example usage
print(minOperations([1,4,1,3], 2))  # expected output: 1
print(minOperations([2,5,5,7], 3))  # expected output: 5
← Back to All Questions