Find the Integer Added to Array I

Easy
987.

Find the Integer Added to Array I

Find the Integer Added to Array I is an easy coding problem on arrays and math, asked in Amazon, Google and Zoho interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var addedInteger = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Integer Added to Array I — Problem & Solution

Find the Integer Added to Array I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Integer Added to Array I is an easy coding problem on arrays and math, asked in Amazon, Google and Zoho interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find the Integer Added to Array I

  1. Hint 1

    Adding the same value to everything shifts the whole array without changing its order.

  2. Hint 2

    So the smallest element of nums1 corresponds to the smallest of nums2.

  3. Hint 3

    The answer is the difference between those two minima.

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)

Java

public static int addedInteger(int[] nums1, int[] nums2) {
    int mn1 = nums1[0], mn2 = nums2[0];
    for (int v : nums1) mn1 = Math.min(mn1, v);
    for (int v : nums2) mn2 = Math.min(mn2, v);
    return mn2 - mn1;
}

C++

int addedInteger(vector<int>& nums1, vector<int>& nums2) {
    int mn1 = *min_element(nums1.begin(), nums1.end());
    int mn2 = *min_element(nums2.begin(), nums2.end());
    return mn2 - mn1;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays