algoadvance

Leetcode 66. Plus One

Problem Statement

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself.

Example:

Clarifying Questions

  1. Can the input array be empty?
    • No, the problem specifies a non-empty array.
  2. Are there negative digits in the array?
    • No, all elements are non-negative digits (0-9).
  3. Is the input array mutable or should I return a new array?
    • You should return a new array with the updated digits.

Strategy

  1. Start from the least significant digit and move towards the most significant digit.
  2. Add one to the least significant digit.
  3. If adding one results in a digit less than 10, you’re done.
  4. If the result is 10, set the current digit to 0 and carry the one to the next more significant digit.
  5. If the most significant digit also results in a carry (i.e., is 10), add a new most significant digit and set it to 1.

Time Complexity

Code

#include <vector>
#include <iostream>

std::vector<int> plusOne(std::vector<int>& digits) {
    // Traverse the digits array starting from the last digit
    int n = digits.size();

    for (int i = n - 1; i >= 0; --i) {
        // If current digit is less than 9, just add one and return the result
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        }
        // Set current digit to 0 and continue to propagate the carry
        digits[i] = 0;
    }

    // If all digits were 9, we will come out of the loop
    // and all digits are now 0, we need an extra leading 1
    digits.insert(digits.begin(), 1);
    return digits;
}

int main() {
    std::vector<int> digits1 = {1, 2, 3};
    std::vector<int> result1 = plusOne(digits1);
    for (int num : result1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> digits2 = {4, 3, 2, 1};
    std::vector<int> result2 = plusOne(digits2);
    for (int num : result2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::vector<int> digits3 = {9, 9, 9};
    std::vector<int> result3 = plusOne(digits3);
    for (int num : result3) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

This implementation traverses the list from the end to the beginning, handling carries as described. If needed, it inserts a 1 at the start of the vector at the end.

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