IT-блоги • Solving a Leetcode problem daily — Day 2: Plus One

Solving a Leetcode problem daily — Day 2: Plus One | by Subhradeep Saha | Apr, 2024 | Medium

Subhradeep Saha ・ Apr 30, 2024 ・

Medium

Here is the Leetcode problem - Plus One

Problem Statement

Imagine you have a very large number stored as an array of digits, where each element in the array represents a single digit of the number. The digits are arranged in big-endian order, meaning the most significant digit (leftmost) is at index 0, and the least significant digit (rightmost) is at the last index. Additionally, there are no leading zeros in this number (according to the constraints).

The challenge is to write a function that takes this array of digits representing a large integer and increments the number by 1. The function should then return a new vector containing the digits of the incremented number.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

• The input array (digits) will have a size between 1 and 100 (inclusive).

• Each element (digits[i]) of the array will be a digit between 0 and 9 (inclusive).

• There will be no leading zeros in the input array.

Understanding the Solution

Here’s a breakdown of the C++ code to solve this problem, explained line by line:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int idx = digits.size()-1;
        int carry = 1;

        while(idx >= 0) {
            int sum = digits[idx] + carry;
            if(sum < 10) {
                digits[idx] = sum;
                return digits;
            }
            digits[idx--] = sum % 10;
            carry = sum / 10;
        }

        if(idx == -1) {
            digits.insert(digits.begin(), carry);
        }
        return digits;
    }
};

Breakdown of the Code:

1. Function Definition:

class Solution {
public:
  vector<int> plusOne(vector<int>& digits) {

This function takes a reference to a vector of integers (digits) representing the large integer and returns a new vector containing the digits of the incremented number.

2. Initialization:

int idx = digits.size()-1;
int carry = 1;

We get the last index of the digits array and store it in idx. This will be used for iterating through the digits in reverse order.
We initialize a variable carry to 1, representing the increment value we want to add.

3. Carry-Over Logic:

while(idx >= 0) {
      int sum = digits[idx] + carry;
      if(sum < 10) {
        digits[idx] = sum;
        return digits;
      }
      digits[idx--] = sum % 10;
      carry = sum / 10;

}

• Looping and Sum: We use a while loop to iterate through the digits array as long as idx is not negative (i.e., we haven't reached the beginning of the array). Inside the loop, we calculate the sum by adding the current digit (digits[idx]) and the carry.
• Early Return (No Carry-Over): If the sum is less than 10, it means there's no carry-over needed. We update the current digit (digits[idx]) with the sum and directly return the modified digits vector.
• Updating Digit and Carry-Over: If the sum is 10 or greater, it signifies a carry-over. We update the current digit (digits[idx]). We use the modulo operator (%) to extract the digit at the current position (sum % 10). This digit is placed back into the corresponding element of the digits array.
• We calculate the carry-over value (sum / 10) using integer division. This value is stored in the carry variable for the next iteration.
• We decrement idx to move to the previous digit in the next iteration.

4. Overflow Case:

if(idx == -1) {
      digits.insert(digits.begin(), carry);
}
return digits;

• Overflow Check: If the loop finishes iterating without returning (meaning idx becomes -1), it signifies an overflow case. This happens when the original number is so large that incrementing it by 1 requires an extra digit at the beginning (most significant position).
• Adding a New Digit: To handle this, we use the insert function of the vector class. We insert the carry value (which is 1 in this case) at the beginning (digits.begin()) of the digits vector. This effectively adds a new digit to the most significant position.

Test Cases
Let’s see how the code works with different input scenarios:

Test Case 1:

digits = [1,2,3]
Expected Output: [1,2,4]
Explanation: Adding 1 to 123 results in 124. The code iterates through the digits, updates them accordingly, and no overflow occurs.

Test Case 2:

digits = [9]
Expected Output: [1,0]
Explanation: Adding 1 to 9 results in 10. The code handles the carry-over, updates the digit to 0 in the original array, and no overflow occurs.

Test Case 3:

digits = [9,9]
Expected Output: [1,0,0]
Explanation: Adding 1 to 99 results in 100. The code handles the carry-over twice, updating digits to 0 and adding a new digit (1) at the beginning to accommodate the overflow.

Real life applications of the problem

The concept of incrementing large integers represented as arrays of digits has various applications in the software world, here are a few examples:

1. Financial Transactions:
In finance systems, large numbers representing money amounts are often stored as arrays of digits for efficiency. When processing transactions that involve adding or subtracting money, incrementing or decrementing these arrays becomes necessary.

2. Counters and Statistics:
Many applications use counters to track various events or metrics. These counters can be represented as arrays of digits, especially when dealing with very large numbers. Incrementing these counters involves manipulating the digits in the array.

3. Large Number Arithmetic:
Libraries or custom functions for performing arbitrary precision arithmetic (calculations with very large numbers) might use arrays of digits to represent the operands (numbers involved in the calculation). Incrementing a number in such a library would involve manipulating the digit array.

4. Big Data Processing:
In big data processing, large datasets may contain numerical values like timestamps, user IDs, or counts. These values can be stored efficiently in arrays of digits. When iterating through such data and needing to update specific values (e.g., incrementing a count), the concept of incrementing digit arrays becomes relevant.

5. Cryptography:
Some cryptographic algorithms involve manipulating large integers. While not directly incrementing, these algorithms might require adding or subtracting large numbers, which could be implemented using digit array manipulation techniques similar to this problem.

It’s important to note that in modern software development, libraries or frameworks often handle large number manipulation behind the scenes. However, understanding the underlying concepts, like incrementing digit arrays, can be valuable for low-level programming, performance optimizations, or simply for a deeper grasp of how computers handle large numbers.

Conclusion

This C++ code efficiently increments a large integer represented as an array of digits by handling carry-over logic and potential overflow situations. By understanding the code and the test cases, you can now tackle similar problems that involve digit manipulation and array operations. Feel free to experiment with different input scenarios and challenge yourself further!