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 Number of Operations to Make Arrays Similar

Number: 2539

Difficulty: Hard

Paid? No

Companies: Amazon, Walmart Labs

Problem Description

You are given two positive integer arrays, nums and target, of the same length. In one operation, you can choose any two distinct indices i and j and perform the following: • Increase nums[i] by 2 • Decrease nums[j] by 2
Arrays are considered similar if they have the same frequency of each element (i.e. they are a permutation of each other). Return the minimum number of operations required to make nums similar to target. It is guaranteed that it is possible to transform nums into an array similar to target.

Key Insights

  • Since each operation adds 2 to one element and subtracts 2 from another, the parity (even/odd) of each element remains unchanged.
  • nums can only be rearranged to match target if the counts of even and odd numbers in each are the same.
  • Group elements by parity (even and odd), and sort these groups in both arrays.
  • For each matching pair in the same parity group, calculate the number of "2-steps" required to balance the difference.
  • Only consider the surplus differences (where an element in nums is larger than the corresponding element in target). The total operations required for a parity group are the sum of these surplus differences (each divided by 2), and the overall answer is the sum over both parity groups.
  • This pairing approach is based on the insight that each operation simultaneously “fixes” one surplus and one deficit across the same parity group.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the groups (n is the length of the arrays)
Space Complexity: O(n) to store the parity-separated arrays

Solution

The solution works as follows:

  1. Split the two arrays into even numbers and odd numbers.
  2. Sort the even parts of nums and target separately. Do the same for the odd parts.
  3. For each pair in the even and odd groups, compute the difference. Only differences where nums[i] exceeds target[i] contribute to the surplus.
  4. Since each operation transfers exactly 2 units and fixes one surplus and one deficit at the same time, the minimum number of operations for a group is the sum of surplus differences divided by 2.
  5. The final answer is the sum of operations needed for both parity groups.

Key data structures used include lists (or arrays) for keeping separate groups. The algorithmic approach is a combination of sorting (to pair corresponding numbers by parity) and a greedy calculation of adjustments.

Code Solutions

# Python solution

def makeSimilar(nums, target):
    # Helper function to separate numbers by parity and sort them
    def get_sorted_by_parity(arr, predicate):
        return sorted([num for num in arr if predicate(num)])
    
    # Separate and sort even and odd numbers for both arrays.
    nums_even = get_sorted_by_parity(nums, lambda x: x % 2 == 0)
    nums_odd = get_sorted_by_parity(nums, lambda x: x % 2 == 1)
    target_even = get_sorted_by_parity(target, lambda x: x % 2 == 0)
    target_odd = get_sorted_by_parity(target, lambda x: x % 2 == 1)
    
    operations = 0
    
    # Calculate surplus operations for each parity group.
    for a, b in zip(nums_even, target_even):
        if a > b:
            # (a - b) is guaranteed to be even; dividing by 2 gives the number of operations needed for that index.
            operations += (a - b) // 2
    
    for a, b in zip(nums_odd, target_odd):
        if a > b:
            operations += (a - b) // 2
            
    return operations

# Example usage:
print(makeSimilar([8,12,6], [2,14,10]))  # Output: 2
print(makeSimilar([1,2,5], [4,1,3]))       # Output: 1
print(makeSimilar([1,1,1,1,1], [1,1,1,1,1]))  # Output: 0
← Back to All Questions