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 <= 1000 <= nums1[i], nums2[i] <= 1000The 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
Hint 1
Adding the same value to everything shifts the whole array without changing its order.
Hint 2
So the smallest element of
nums1corresponds to the smallest ofnums2.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
- Find the smallest value in each array.
- 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
nums2may be in a different order. xcan 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