LeetCode problem#66

Plus One

Solved in 1 languageC#

71 lines

1using System.Collections.Generic;
2
3class Solution
4{
5    // time O(n)
6    public int[] PlusOne(int[] digits)
7    {
8        for (int i = digits.Length - 1; i >= 0; --i)
9        {
10            if (digits[i] < 9)
11            {
12                digits[i] = digits[i] + 1;
13                return digits;
14            }
15            else
16            {
17                digits[i] = 0;
18            }
19        }
20
21        // Array is initialized with zero values
22        digits = new int[digits.Length + 1];
23        digits[0] = 1;
24
25        return digits;
26    }
27}
28
29class Driver
30{
31    static void Main()
32    {
33        Test();
34    }
35
36    static void AssertEqual(int actual, int expected)
37    {
38        if (actual != expected)
39        {
40            throw new System.Exception(string.Format("Expected {0}, but got {1}", expected, actual));
41        }
42    }
43
44    static void Test()
45    {
46        var solution = new Solution();
47        int[] testcase1 = solution.PlusOne(new int[] { 1, 2, 3 });
48        AssertEqual(testcase1[0], 1);
49        AssertEqual(testcase1[1], 2);
50        AssertEqual(testcase1[2], 4);
51        AssertEqual(testcase1.Length, 3);
52        
53        int[] testcase2 = solution.PlusOne(new int[] { 4, 3, 2, 1 });
54        AssertEqual(testcase2[0], 4);
55        AssertEqual(testcase2[1], 3);
56        AssertEqual(testcase2[2], 2);
57        AssertEqual(testcase2[3], 2);
58        AssertEqual(testcase2.Length, 4);
59
60        int[] testcase3 = solution.PlusOne(new int[] { 9 });
61        AssertEqual(testcase3[0], 1);
62        AssertEqual(testcase3[1], 0);
63        AssertEqual(testcase3.Length, 2);
64
65        int[] testcase4 = solution.PlusOne(new int[] { 9, 9 });
66        AssertEqual(testcase4[0], 1);
67        AssertEqual(testcase4[1], 0);
68        AssertEqual(testcase4[2], 0);
69        AssertEqual(testcase4.Length, 3);
70    }
71}

How it works

The provided code is a C# implementation of a solution to the "Plus One" problem on LeetCode, which is commonly used to test understanding of array manipulation and handling of integer carry. The problem involves incrementing a number represented by an array of its digits, such that each element of the array corresponds to a single digit, and the most significant digit is at the beginning of the array.

Problem Description

Given an array of integers digits, where each integer represents a single digit of a number (from most significant to least significant), you need to increment this number by one and return the resulting number as an array of digits.

Solution Explanation

Here’s a step-by-step breakdown of the solution provided in the PlusOne method:

Iterate Backwards: The method starts a loop from the last digit (least significant) to the first. This is crucial because when incrementing a number, you usually start from the rightmost position.
```
for (int i = digits.Length - 1; i >= 0; --i)
```
Check for Carrying:
- If the current digit is less than 9, it can be incremented without any carry. The method simply adds 1 to that digit, then returns the modified array.
```
1if (digits[i] < 9)
2{
3    digits[i] = digits[i] + 1;
4    return digits;
5}
```
- If the digit is 9, incrementing it would cause it to roll over to 0, so we set the current digit to 0 and continue to the next more significant digit (left).
```
1else
2{
3    digits[i] = 0;
4}
```
Handling the Overflow: If all digits are 9, the loop will exit after setting all of them to 0. In this case, the array needs to be expanded because the result will have an additional most significant digit (which will be 1, followed by zeros). Therefore, a new array is created, which is one element larger, and the first element is set to 1.
```
digits = new int[digits.Length + 1];
digits[0] = 1;
```
Return Result: Finally, the method returns the modified digits array, which represents the new number.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of digits in the input array. This is because in the worst case, we may potentially traverse all the digits of the array.

Driver and Test Code Explanation

The Driver class is used to run the test cases to ensure the implementation works correctly. It defines several test conditions in Test() method, calling PlusOne on various test arrays and asserting that the output matches expected results using AssertEqual.
Each test checks both the values in the resulting array and its length to ensure that the increment has been performed correctly.

Summary

This solution effectively handles all scenarios, including normal cases where the last digit can be incremented without carry, and edge cases where the entire number consists of nines. It demonstrates clear array manipulation and understanding of carry arithmetic.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.