algoadvance

Leetcode 3131. Find the Integer Added to Array I

Problem Statement

You are given an integer array original and another integer array added which is identical to original with exactly one integer added to it. Your task is to find the integer that was added to original to get added.

Clarifying Questions

1. Can the added integer be a duplicate of an integer already present in the original array?
   • Yes, it can be a duplicate.
2. What will be the size constraints on the original array?
   • You can assume the length of original will be at least 1 and at most 10^5.
3. Will the integer values in the arrays be within a certain range?
   • The integers in the arrays will be within the range of Java’s int type, which is -2^31 to 2^31-1.

Strategy

1. Sum Comparison: One straightforward approach is to find the sum of the elements in both arrays, and the difference between the sum of added and the sum of original will be the extra integer.
2. HashMap Counting: Another approach is to use a HashMap to count occurrences of each number in original and added. The element which has a higher count in added is the one that was added.

We will implement the first approach because it is simpler and has better performance characteristics for this problem size.

Code

public class FindAddedNumber {
    public int findAddedNumber(int[] original, int[] added) {
        int sumOriginal = 0;
        for (int num : original) {
            sumOriginal += num;
        }

        int sumAdded = 0;
        for (int num : added) {
            sumAdded += num;
        }

        return sumAdded - sumOriginal;
    }

    public static void main(String[] args) {
        FindAddedNumber sol = new FindAddedNumber();
        int[] original = {4, 1, 3};
        int[] added = {4, 1, 3, 7};
        System.out.println(sol.findAddedNumber(original, added)); // Output: 7
    }
}

Time Complexity

• The approach runs in O(n) time, where n is the number of elements in the original array (since the added array is n+1 elements).
• The space complexity is O(1) since we are using a few extra variables but not any additional data structures that scale with input size.

This solution is efficient and straightforward for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?