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

Minimum Operations to Make Array Equal II

Number: 2604

Difficulty: Medium

Paid? No

Companies: Walmart Labs

Problem Description

Given two integer arrays nums1 and nums2 of equal length and an integer k, you can perform operations on nums1. In each operation, you select two indices i and j and update nums1 by incrementing nums1[i] by k and decrementing nums1[j] by k. The goal is to determine the minimum number of operations needed to transform nums1 into nums2. If it is impossible, return -1.

Key Insights

  • Each operation transfers a fixed unit (k) from one index to another while preserving the overall sum.
  • The total change required (diff = nums2[i] - nums1[i]) for each element must be divisible by k if k > 0.
  • When k is zero, no changes can be made, so the arrays must already be equal.
  • Convert each difference into units by dividing by k. The sum of these units across all indices must be zero; otherwise, it is impossible to balance the adjustments.
  • The minimum number of operations is equal to the total positive units needed (which equals the total negative units in absolute value).

Space and Time Complexity

Time Complexity: O(n) – One pass through the arrays to compute the differences and validate conditions. Space Complexity: O(1) – Uses a constant amount of additional space.

Solution

We start by checking whether k is zero; if so, we return 0 if nums1 already equals nums2 or -1 if not. For k > 0, calculate the difference diff = nums2[i] - nums1[i] for each index. If diff is not divisible by k for any element, return -1. Otherwise, convert the diff into units by diff / k and accumulate these units. If the sum of all units is not zero, the transformation is impossible. The answer is then the sum of all positive units, which represents the minimum number of k-unit transfers required to achieve the target array.

Code Solutions

def min_operations(nums1, nums2, k):
    # If k is zero, no operations can change the array, so they must be equal.
    if k == 0:
        return 0 if nums1 == nums2 else -1
    
    total_transfer = 0  # Sum of unit differences; must be 0 for a valid transformation.
    operations_needed = 0  # Minimum operations required.
    
    # Process each index to calculate differences in units.
    for a, b in zip(nums1, nums2):
        diff = b - a
        if diff % k != 0:  # If diff cannot be reached using multiples of k, return -1.
            return -1
        unit = diff // k
        total_transfer += unit
        if unit > 0:
            operations_needed += unit  # Only positive transfers count as required operations.
    
    # Overall balance check: if total_transfer is not 0, the adjustments don't cancel out.
    if total_transfer != 0:
        return -1
    return operations_needed

# Example usage:
print(min_operations([4,3,1,4], [1,3,7,1], 3))  # Expected output: 2
print(min_operations([3,8,5,2], [2,4,1,6], 1))  # Expected output: -1
← Back to All Questions