algoadvance

Leetcode 3131. Find the Integer Added to Array I

Problem Statement

Given an integer array nums, find the integer that was added to the array. Initially, the array consists of the numbers from 1 to n, but one number has been added to the array. Return the integer that was added to the array.

Example:

Input: nums = [4, 1, 3, 2, 6, 5, 7, 8]
Output: 6

Clarifying Questions

  1. What is the size range for the input array nums?
    • The size is n + 1, where n represents the range from 1 to n.
  2. Are all elements in the input array unique besides the added one?
    • Yes, besides the added integer, all elements are unique and within the range 1 to n.
  3. Can the added integer be from outside the range of 1 to n?
    • No, the integer added will be one of the integers ranging from 1 to n.

Strategy

To solve this problem efficiently:

  1. Calculate the expected sum of the first n natural numbers using the formula: [ \text{sum}_\text{expected} = \frac{n \cdot (n + 1)}{2} ]

  2. Calculate the sum of all elements present in the nums array: [ \text{sum}_\text{actual} ]

  3. The integer that was added will be the difference: [ \text{added\ integer} = \text{sum}\text{actual} - \text{sum}\text{expected} ]

Code

#include <vector>
#include <numeric>  // for accumulate function

int findAddedInteger(const std::vector<int>& nums) {
    int n = nums.size() - 1;
    int sum_expected = n * (n + 1) / 2;
    int sum_actual = std::accumulate(nums.begin(), nums.end(), 0);
    return sum_actual - sum_expected;
}

int main() {
    std::vector<int> nums = {4, 1, 3, 2, 6, 5, 7, 8};
    int result = findAddedInteger(nums);
    std::cout << "The added integer is: " << result << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the size of the array minus 1. This is because:

The space complexity is O(1) as we are using a fixed amount of extra space regardless of the input size.

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