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

Equal Sum Arrays With Minimum Number of Operations

Number: 1901

Difficulty: Medium

Paid? No

Companies: American Express

Problem Description

Given two arrays of integers, nums1 and nums2, where each integer is between 1 and 6 (inclusive), we can perform operations where we change any element in either array to any value between 1 and 6. The goal is to make the sums of the two arrays equal using the minimum number of operations, or return -1 if it is impossible.

Key Insights

  • Determine which array has the smaller sum and which has the larger sum.
  • The maximum adjustment per operation is 5 (either increasing a 1 to a 6 or decreasing a 6 to a 1).
  • Use a greedy approach by selecting the operation that provides the maximum change (gain) first.
  • Calculate all possible gains from both arrays: for the smaller-sum array, the gain is (6 - current_val) and for the larger-sum array, it is (current_val - 1).
  • Sort these gains in descending order and apply them until the sum difference is closed.

Space and Time Complexity

Time Complexity: O(n) where n is the total number of elements in the two arrays. This covers summing the arrays and building and sorting the gains (sorting is O(n log n), but n is limited by constant factors due to the restricted range of values). Space Complexity: O(1) using extra space proportional to the size of gains, but since numbers range from 1 to 6, the counts can be managed with a fixed-size array if optimized further.

Solution

The solution follows these steps:

  1. Calculate the sums of the two arrays.
  2. If the sums are equal, return 0.
  3. Swap the arrays if needed so that nums1 always has the smaller sum.
  4. Compute the difference (diff) between the larger and smaller sums.
  5. For each element in nums1, determine the maximum gain by changing it to 6 (gain = 6 - element).
  6. For each element in nums2, determine the maximum gain by changing it to 1 (gain = element - 1).
  7. Combine all gains, sort them in descending order.
  8. Iteratively subtract the largest available gain from diff, and count the operations.
  9. If diff becomes 0 or negative, return the number of operations; otherwise, return -1 if all gains are exhausted.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def minOperations(self, nums1, nums2):
        # Calculate the sums of both arrays
        sum1, sum2 = sum(nums1), sum(nums2)
        
        # If the sums are already equal, no operations are needed
        if sum1 == sum2:
            return 0
        
        # Ensure that nums1 has the smaller sum
        if sum1 > sum2:
            return self.minOperations(nums2, nums1)
        
        # Compute the difference that needs to be closed
        diff = sum2 - sum1
        
        # List to store all possible gains
        gains = []
        
        # For elements in nums1, the maximum gain is increasing them to 6
        for num in nums1:
            gains.append(6 - num)
        
        # For elements in nums2, the maximum gain is decreasing them to 1
        for num in nums2:
            gains.append(num - 1)
        
        # Sort the gains in descending order to use the largest gains first
        gains.sort(reverse=True)
        
        operations = 0
        # Apply the greedy approach using the largest available gain first
        for gain in gains:
            diff -= gain
            operations += 1
            # If the difference has been closed or reversed, return the count of operations
            if diff <= 0:
                return operations
        
        # If unable to close the gap, return -1
        return -1
← Back to All Questions