3131. Find the Integer Added to Array I - Solution

Q: Is Find the Integer Added to Array I easy or hard?

Find the Integer Added to Array I is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The challenge mainly tests whether you recognize that adding a constant shifts all values uniformly, allowing a simple arithmetic comparison.

Q: Find the Integer Added to Array I Python/Java solution

In Python or Java, iterate through the arrays to compute either the minimum value or the sum. For the min-based solution, calculate min(nums2) - min(nums1). Both implementations run in O(n) time and require constant extra space.

Q: How to solve Find the Integer Added to Array I in O(n)?

Traverse both arrays once. Compute either the minimum values or the total sums of each array. If using the minimum method, return min(nums2) minus min(nums1). If using the sum method, compute (sum(nums2) - sum(nums1)) divided by n, where n is the array length.

Q: What is the best approach for Find the Integer Added to Array I?

The most direct approach computes the difference between the minimum elements of nums2 and nums1. Because adding a constant shifts every value equally, the smallest element increases by the same amount. This method runs in O(n) time and O(1) space and requires only a single pass through both arrays.

Q: Is Find the Integer Added to Array I asked at Google/Amazon/Meta?

This problem is categorized as an easy array and math question, similar to screening problems used in early interview rounds. Variations that involve constant shifts, array comparisons, or difference calculations appear frequently in coding interviews across major tech companies.

Q: What data structure is used in Find the Integer Added to Array I?

The solution relies only on basic array traversal. No additional data structures such as hash maps or stacks are required. The algorithm tracks either the minimum element or the cumulative sum while iterating through the arrays.

Q: What is the time complexity of Find the Integer Added to Array I?

The optimal solution runs in O(n) time since you only scan each array once to compute either the minimum or the sum. Space complexity is O(1) because the algorithm stores only a few variables regardless of input size.

The problem

You are given two arrays of equal length, nums1 and nums2.

Each element in nums1 has been increased (or decreased in the case of negative) by an integer, represented by the variable x.

As a result, nums1 becomes equal to nums2. Two arrays are considered equal when they contain the same integers with the same frequencies.

Return the integer x.

Example 1:

Input: nums1 = [2,6,4], nums2 = [9,7,5]

Output: 3

Explanation:

The integer added to each element of nums1 is 3.

Example 2:

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

Output: -5

Explanation:

The integer added to each element of nums1 is -5.

Example 3:

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

Output: 0

Explanation:

The integer added to each element of nums1 is 0.

Constraints:

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

Approach overview

Problem Overview: You receive two integer arrays nums1 and nums2. Every element in nums1 had the same integer added to it, producing nums2. Your job is to determine that integer. The order of elements may differ, so the solution relies on properties that remain unchanged when a constant value is added to every element.

Approach 1: Difference Calculation Approach (O(n) time, O(1) space)

The key observation: adding the same integer x to every element shifts the entire array by the same amount. The smallest value in nums1 becomes the smallest value in nums2 after adding x. Compute min(nums1) and min(nums2), then return x = min(nums2) - min(nums1). This works even if the arrays are reordered because the relative ordering of elements does not change after adding a constant. You only need one pass to compute the minimum of each array, making this a clean linear-time solution using basic array traversal.

Approach 2: Average Difference Approach (O(n) time, O(1) space)

Another property of adding a constant to all elements is that the total sum increases by n * x, where n is the array length. Compute sum(nums1) and sum(nums2), then derive the value using x = (sum(nums2) - sum(nums1)) / n. This approach relies on simple arithmetic and avoids sorting or element comparisons. It’s essentially a math-based observation applied during a single pass through the arrays.

Recommended for interviews: The Difference Calculation approach is typically preferred because it is simple, intuitive, and avoids division. Interviewers expect you to recognize that adding a constant shifts the minimum value by the same amount. The Average Difference method also works and demonstrates a good understanding of array sums, but the minimum-difference observation usually surfaces faster during interviews.

Approach 1: Difference Calculation Approach

The simplest approach to find the integer x is to calculate the difference between corresponding elements of nums2 and nums1. Since it's given that both arrays nums1 and nums2 will be equal after adding x to nums1, the value of x remains constant across all pairs of elements. Therefore, for any valid i, x = nums2[i] - nums1[i].

Python

def find_added_integer(nums1, nums2):
    return nums2[0] - nums1[0]

nums1 = [2,6,4]
nums2 = [9,7,5]
print(find_added_integer(nums1, nums2))

Java

public class Solution {
    public static int findAddedInteger(int[] nums1, int[] nums2) {
        return nums2[0] - nums1[0];
    }
    public static void main(String[] args) {
        int[] nums1 = {2,6,4};
        int[] nums2 = {9,7,5};
        System.out.println(findAddedInteger(nums1, nums2));
    }
}

C++

#include <iostream>
#include <vector>

int findAddedInteger(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    return nums2[0] - nums1[0];
}

int main() {
    std::vector<int> nums1 = {2,6,4};
    std::vector<int> nums2 = {9,7,5};
    std::cout << findAddedInteger(nums1, nums2) << std::endl;
    return 0;
}

JavaScript

function findAddedInteger(nums1, nums2) {
    return nums2[0] - nums1[0];
}

const nums1 = [2,6,4];
const nums2 = [9,7,5];
console.log(findAddedInteger(nums1, nums2));

#include <stdio.h>

int findAddedInteger(int nums1[], int nums2[], int length) {
    return nums2[0] - nums1[0];
}

int main() {
    int nums1[] = {2,6,4};
    int nums2[] = {9,7,5};
    int length = 3;
    printf("%d\n", findAddedInteger(nums1, nums2, length));
    return 0;
}

using System;

public class Solution {
    public static int FindAddedInteger(int[] nums1, int[] nums2) {
        return nums2[0] - nums1[0];
    }

    public static void Main(string[] args) {
        int[] nums1 = {2,6,4};
        int[] nums2 = {9,7,5};
        Console.WriteLine(FindAddedInteger(nums1, nums2));
    }
}

The Python implementation is straightforward, leveraging the difference between the corresponding first elements of the input arrays to find and return x.

Complexity

Time Complexity: O(1) for accessing the first element.
Space Complexity: O(1), requires no extra storage.

Try this approach in the editor

Approach 2: Average Difference Approach

An alternative approach involves finding the integer added by calculating the average difference between the corresponding elements of nums1 and nums2. This approach is more of a verification of intent since we expect consistent differences based on problem constraints.

Python

def find_added_integer(nums1, nums2):
    sum_diff = sum(b - a for a, b in zip(nums1, nums2))
    return sum_diff // len(nums1)

nums1 = [2,6,4]
nums2 = [9,7,5]
print(find_added_integer(nums1, nums2))

Java

public class Solution {
    public static int findAddedInteger(int[] nums1, int[] nums2) {
        int sumDiff = 0;
        for (int i = 0; i < nums1.length; i++) {
            sumDiff += nums2[i] - nums1[i];
        }
        return sumDiff / nums1.length;
    }
    public static void main(String[] args) {
        int[] nums1 = {2,6,4};
        int[] nums2 = {9,7,5};
        System.out.println(findAddedInteger(nums1, nums2));
    }
}

C++

#include <iostream>
#include <vector>

int findAddedInteger(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    int sum_diff = 0;
    for (size_t i = 0; i < nums1.size(); ++i) {
        sum_diff += nums2[i] - nums1[i];
    }
    return sum_diff / nums1.size();
}

int main() {
    std::vector<int> nums1 = {2,6,4};
    std::vector<int> nums2 = {9,7,5};
    std::cout << findAddedInteger(nums1, nums2) << std::endl;
    return 0;
}

JavaScript

function findAddedInteger(nums1, nums2) {
    let sumDiff = 0;
    for (let i = 0; i < nums1.length; i++) {
        sumDiff += nums2[i] - nums1[i];
    }
    return sumDiff / nums1.length;
}

const nums1 = [2,6,4];
const nums2 = [9,7,5];
console.log(findAddedInteger(nums1, nums2));

#include <stdio.h>

int findAddedInteger(int nums1[], int nums2[], int length) {
    int sum_diff = 0;
    for (int i = 0; i < length; ++i) {
        sum_diff += nums2[i] - nums1[i];
    }
    return sum_diff / length; // Though constraints assure us this is constant
}

int main() {
    int nums1[] = {2,6,4};
    int nums2[] = {9,7,5};
    int length = 3;
    printf("%d\n", findAddedInteger(nums1, nums2, length));
    return 0;
}

using System;

public class Solution {
    public static int FindAddedInteger(int[] nums1, int[] nums2) {
        int sumDiff = 0;
        for (int i = 0; i < nums1.Length; i++) {
            sumDiff += nums2[i] - nums1[i];
        }
        return sumDiff / nums1.Length;
    }

    public static void Main(string[] args) {
        int[] nums1 = {2,6,4};
        int[] nums2 = {9,7,5};
        Console.WriteLine(FindAddedInteger(nums1, nums2));
    }
}

The Python function calculates the total difference of each element in nums1 from nums2 and divides it by the array size, deriving x.

Complexity

Time Complexity: O(n) because each element is iterated through.
Space Complexity: O(1), uses simple arithmetic operations.

Try this approach in the editor

Approach 3: Calculate Minimum Difference

We can find the minimum value of each array, then return the difference between the two minimum values.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function addedInteger(nums1: number[], nums2: number[]): number {
    return Math.min(...nums2) - Math.min(...nums1);
}

func addedInteger(nums1 []int, nums2 []int) int {
	return slices.Min(nums2) - slices.Min(nums1)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Difference Calculation Approach	Time Complexity: O(1) for accessing the first element. Space Complexity: O(1), requires no extra storage.
Average Difference Approach	Time Complexity: O(n) because each element is iterated through. Space Complexity: O(1), uses simple arithmetic operations.
Calculate Minimum Difference	–

Complexity analysis

Approach	Time	Space	When to Use
Difference Calculation (Min Difference)	O(n)	O(1)	Best general solution. Works even if arrays are reordered and requires only min comparisons.
Average Difference (Sum Method)	O(n)	O(1)	Useful when reasoning with sums or when minimum values are not directly considered.

Frequently asked questions

Is Find the Integer Added to Array I easy or hard?

Find the Integer Added to Array I is classified as an Easy problem on LeetCode with an acceptance rate above 80%. The challenge mainly tests whether you recognize that adding a constant shifts all values uniformly, allowing a simple arithmetic comparison.

Find the Integer Added to Array I Python/Java solution

In Python or Java, iterate through the arrays to compute either the minimum value or the sum. For the min-based solution, calculate min(nums2) - min(nums1). Both implementations run in O(n) time and require constant extra space.

How to solve Find the Integer Added to Array I in O(n)?

Traverse both arrays once. Compute either the minimum values or the total sums of each array. If using the minimum method, return min(nums2) minus min(nums1). If using the sum method, compute (sum(nums2) - sum(nums1)) divided by n, where n is the array length.

What is the best approach for Find the Integer Added to Array I?

The most direct approach computes the difference between the minimum elements of nums2 and nums1. Because adding a constant shifts every value equally, the smallest element increases by the same amount. This method runs in O(n) time and O(1) space and requires only a single pass through both arrays.

Is Find the Integer Added to Array I asked at Google/Amazon/Meta?

This problem is categorized as an easy array and math question, similar to screening problems used in early interview rounds. Variations that involve constant shifts, array comparisons, or difference calculations appear frequently in coding interviews across major tech companies.

What data structure is used in Find the Integer Added to Array I?

The solution relies only on basic array traversal. No additional data structures such as hash maps or stacks are required. The algorithm tracks either the minimum element or the cumulative sum while iterating through the arrays.

What is the time complexity of Find the Integer Added to Array I?

The optimal solution runs in O(n) time since you only scan each array once to compute either the minimum or the sum. Space complexity is O(1) because the algorithm stores only a few variables regardless of input size.

Find the Integer Added to Array I solution and explanation

The problem

Approach overview

Approach 1: Difference Calculation Approach

Approach 2: Average Difference Approach

Approach 3: Calculate Minimum Difference

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Integer Added to Array I solution and explanation

The problem

Approach overview

Approach 1: Difference Calculation Approach

Approach 2: Average Difference Approach

Approach 3: Calculate Minimum Difference

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems