algoadvance

Leetcode 989. Add to Array

Problem Statement

The problem is to perform addition on an array-form representation of an integer and another integer. Specifically:

The array-form of an integer num is an array representing its digits in left-to-right order. For example, for num = 1234, the array-form is [1, 2, 3, 4]. Given an array num and an integer k, return the array-form of the integer num + k.

Example:

Input: num = [1, 2, 0, 0], k = 34
Output: [1, 2, 3, 4]

Input: num = [2, 7, 4], k = 181
Output: [4, 5, 5]

Input: num = [2, 1, 5], k = 806
Output: [1, 0, 2, 1]

Constraints:

Clarifying Questions

  1. Is the num array guaranteed to be non-empty?
  2. Should we consider leading zeros in the result?
  3. Can k be negative, or is it always positive as stated in the constraints?

(Assuming the problem constraints and conditions are as per the problem statement: num is non-empty, positive integer k, and no leading zeros).

Strategy

To solve this problem efficiently, we can simulate the process of adding two numbers digit by digit, much like how you would perform addition manually.

Here’s the step-by-step process:

  1. Start from the least significant digit (end of the array num) and add k to it.
  2. Use a carry mechanism to handle sums greater than 10.
  3. Continue the process for all digits of num. If after processing all digits there is still a carry, continue processing the carry until it is zero.
  4. Finally, as we might end up with digits in reverse order, reverse the result at the end before returning.

Code

#include <vector>
#include <algorithm>

std::vector<int> addToArrayForm(std::vector<int>& num, int k) {
    int n = num.size();
    std::vector<int> result;
    int carry = k;

    // Process each digit from the end of the num array
    for (int i = n - 1; i >= 0; --i) {
        int sum = num[i] + carry;
        result.push_back(sum % 10);
        carry = sum / 10;
    }
    
    // Process remaining carry (if any)
    while (carry > 0) {
        result.push_back(carry % 10);
        carry /= 10;
    }
    
    // Since we added digits starting from the end, reverse the result
    std::reverse(result.begin(), result.end());
    
    return result;
}

Time Complexity

The time complexity of this approach is O(n + m), where n is the length of the array num and m is the number of digits in the integer k (in the worst case, adding substantial carry might go beyond n to handle the carry digits).

The space complexity is O(n + m) as well, to store the result which includes all digits of num plus potential additional carry digits.

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