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

Find the Integer Added to Array II

Number: 3399

Difficulty: Medium

Paid? No

Companies: Mitsogo

Problem Description

Given two integer arrays nums1 and nums2, nums1 originally contained two extra elements compared to nums2. After removing two elements from nums1, every remaining element is incremented (or decremented) by an integer x so that the resulting array (as a multiset) becomes equal to nums2. The task is to determine the minimum possible integer x that achieves this equivalence.

Key Insights

  • Removing two elements from nums1 leaves a multiset of size equal to nums2.
  • The transformation is uniform; every element in the remaining nums1 is adjusted by the same integer x.
  • We can utilize the total sum of both arrays. For any removal pair, if S1 is the sum of nums1 and S2 is the sum of nums2, then after removal the sum of the remaining elements is S1 - (removed1 + removed2) and adding x to each of these (n1 - 2) elements gives S2. This yields x = (S2 - (S1 - removed_sum)) / (n1 - 2).
  • Even if x comes out as an integer from the sum formula, we must verify that applying this shift to the remaining numbers exactly reproduces the frequency distribution of nums2.
  • With n1 up to 200, we can safely enumerate all O(n1²) pairs for removal.

Space and Time Complexity

Time Complexity: O(n1² * n1) ≈ O(n1³) in the worst-case due to enumerating removal pairs and checking the frequency match for each candidate. Space Complexity: O(n1 + n2) for storing frequency dictionaries (or counters) and temporary arrays.

Solution

We iterate over every possible pair of indices in nums1 representing the two removed elements. For each pair:

  1. Compute the sum of the remaining elements of nums1.
  2. Deduce the candidate x using the relation: x = (S2 - remaining_sum) / (n1 - 2). If it is not an integer, move on.
  3. Apply x to each element of the remaining array, and form its frequency dictionary.
  4. Compare this frequency dictionary with that of nums2. If they match, update the answer.
  5. Finally, return the minimum valid x found.

The approach uses enumeration of candidate pairs with helper data structures, such as hash maps (or Counters), to manage frequency counts.

Code Solutions

# Python solution
from collections import Counter
from math import inf

def findIntegerAdded(nums1, nums2):
    n1 = len(nums1)
    n2 = len(nums2)  # n2 = n1 - 2
    total_nums1 = sum(nums1)
    total_nums2 = sum(nums2)
    target_size = n1 - 2  # number of elements remaining after removal
    nums2_counter = Counter(nums2)
    best_x = inf

    # Enumerate all pairs of indices to remove from nums1
    for i in range(n1):
        for j in range(i + 1, n1):
            removed_sum = nums1[i] + nums1[j]
            remaining_sum = total_nums1 - removed_sum
            # Check if candidate x from the sum equation is integer:
            if (total_nums2 - remaining_sum) % target_size != 0:
                continue
            x_candidate = (total_nums2 - remaining_sum) // target_size
            
            # Build counter for the adjusted remaining elements after applying x
            adjusted_counter = Counter()
            for k in range(n1):
                if k == i or k == j:
                    continue  # skip removed elements
                adjusted_value = nums1[k] + x_candidate
                adjusted_counter[adjusted_value] += 1
            
            # If the counters match, we have a valid candidate x
            if adjusted_counter == nums2_counter:
                best_x = min(best_x, x_candidate)
    
    return best_x if best_x != inf else None

# Example usage:
print(findIntegerAdded([4,20,16,12,8], [14,18,10]))  # Output: -2
print(findIntegerAdded([3,5,5,3], [7,7]))              # Output: 2
← Back to All Questions