Find the Integer Added to Array I — Easy Problem & Solution

Problem statement

nums1 and nums2 have the same length. Every element of nums1 was increased — or decreased — by the same integer x, and the result, reordered, is nums2.

Return x.

Example 1

Input: nums1 = [2,6,4], nums2 = [9,7,5]
Output: 3
Explanation: Adding 3 turns `[2,6,4]` into `[5,9,7]`.

Example 2

Input: nums1 = [10], nums2 = [5]
Output: -5

Example 3

Input: nums1 = [1,1,1,1], nums2 = [1,1,1,1]
Output: 0

Constraints

• 1 <= nums1.length == nums2.length <= 100
• 0 <= nums1[i], nums2[i] <= 1000
• The test cases are generated so that there is an integer x such that nums1 can become equal to nums2 by adding x to each element of nums1.

How to solve Find the Integer Added to Array I

A constant shift maps the minimum to the minimum, so x is min(nums2) - min(nums1).

Approach

1. Find the smallest value in each array.
2. Return their difference.

Why it works

Adding a constant is order-preserving, which is exactly why the reordering in the statement is harmless: whatever permutation was applied, the smallest of nums2 is still the image of the smallest of nums1. Comparing sums, or any other order statistic, works equally well for the same reason.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Comparing element by element fails, because nums2 may be in a different order.
• x can be negative — the elements may have been decreased.
• Sorting both arrays also works but is more than the problem needs.

Reference solution

Python

from typing import List

def addedInteger(nums1: List[int], nums2: List[int]) -> int:
    return min(nums2) - min(nums1)

JavaScript

var addedInteger = function(nums1, nums2) {
    var mn1 = nums1[0], mn2 = nums2[0], i;
    for (i = 1; i < nums1.length; i++) if (nums1[i] < mn1) mn1 = nums1[i];
    for (i = 1; i < nums2.length; i++) if (nums2[i] < mn2) mn2 = nums2[i];
    return mn2 - mn1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy