Plus One
Tags: algorithms, csharp, leetcode, easy
Published: 2022-10-19 05:44:29

_#66.Plus One_

### Problem statement
You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`'s.

Increment the large integer by one and return _the resulting array of digits_.

**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].
```

### Explanation
給定一個整數並以陣列形式表示， 其整數依照常理數字規則開頭不為 0，返回該整數加一後的陣列結果

### Solution
題目好理解，需要考量的地方是進位，其實也很簡單，就是一般數學的加法，先把陣列中的整數轉換成字串，再將字串合併轉換成整數，使用加法運算讓整數直接加一得到結果，最後將字串的結果轉換成整數陣列返回

```csharp
public int[] PlusOne(int[] digits)
{
	string str = "";

	for (int i = 0; i < digits.Length; i++)
		str += digits[i];

	int tmp = int.Parse(str) + 1;

	str = tmp.ToString();

	int[] res = new int[str.Length];

	for (int i = 0; i < str.Length; i++)
		res[i] = int.Parse(str[i].ToString());

	return res;
}
```

測試沒問題提交到 LeetCode 上，結果噴出一個錯誤 `System.OverflowException: Value was either too large or small for a UInt64` ，看起來是在字串轉換成數值時大小不夠，即便換成 `long` 型態也會不夠，考量到這一點，我想應該要換個做法

這次我不用數值相加的運算子來做，我想要直接對陣列進行迭代，並在迭代過程中進行單一位數值的相加，以避免上述的錯誤

首先建立一個 `List<int>` 集合用以儲存結果，以及一個 `bool` 表示是否有進位，透過迴圈走訪陣列，起始值從陣列的最後一個索引開始，因為要從個位數加一，之後在往前判斷是否要進位，第一個 `if` 是用來判斷是否為個位數，如果成立執行相加，`else` 則是個位數以外的位數，`else` 內第一個 `if else` 用來判斷有沒有需要進位，其餘的地方就不加以解釋，純粹只是將結果添加到 `List<int>` 集合中以及紀錄需不需要進位

迴圈結束後還需要在判斷一次有沒有進位，如果有就直接添加 1，舉例 99+1=100，如果沒有這個判斷，`list` 裡的結果會只有 00，而不是 100

最後將 `list` 轉換成陣列，透過原生陣列的反轉方法將其反轉就是答案了

```cs
public int[] PlusOne(int[] digits)
{
	if (digits.Length == 0) return null;

	List<int> list = new List<int>();
	bool carry = false;

	for (int i = digits.Length - 1; i >= 0; i--)
	{
		if (i == digits.Length - 1)
		{
			if (digits[i] + 1 == 10)
			{
				list.Add(0);
				carry = true;
			}
			else
				list.Add(digits[i] + 1);
		}
		else
		{
			if (carry)
			{
				if (digits[i] + 1 == 10)
				{
					list.Add(0);
					carry = true;
				}
				else
				{
					list.Add(digits[i] + 1);
					carry = false;
				}
			}
			else
				list.Add(digits[i]);

		}
	}

	if (carry)
		list.Add(1);

	var res = list.ToArray();

	Array.Reverse(res);

	return res;
}
```

我在寫這篇文章的時候覺得這樣的寫法不太好，於是我將迴圈內的第一個 `if` 判斷拿到迴圈外面執行，才不會每次進到迴圈都需要判斷，這樣的話迴圈的起始值要改成倒數第二個索引開始，其餘的部分沒有什麼差異

```csharp
public int[] PlusOne(int[] digits)
{
	List<int> list = new List<int>();
	bool carry = false;

	int len = digits.Length - 1;

	if (digits[len] + 1 == 10)
	{
		list.Add(0);
		carry = true;
	}
	else list.Add(digits[len] + 1);

	for (int i = len - 1; i >= 0; i--)
	{
		if (carry)
		{
			if (digits[i] + 1 == 10)
				list.Add(0);
			else
			{
				list.Add(digits[i] + 1);
				carry = false;
			}
		}
		else list.Add(digits[i]);
	}

	if (carry) list.Add(1);

	var res = list.ToArray();
	Array.Reverse(res);

	return res;
}
```

### Reference
[LeetCode Solution](https://leetcode.com/problems/plus-one/discuss/1328195/C-Solution)

[GitHub Repository](https://github.com/FakeStandard/LeetCode-CSharp/tree/main/Solution/0066.Plus-one)

---

Thanks for reading the article :tulip: :sunflower: :blossom:

If you like it, please don't hesitate to click heart button :heart:
or click like on my Leetcode solution
or follow my [GitHub](https://github.com/FakeStandard) :star:
or buy me a coffee :arrow_down: I'd appreciate it.

[![Buy-me-a-coffee][1]][2]

[1]: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h077sxd0vx1hix4t7lw8.png
[2]: https://www.buymeacoffee.com/FakeStandard

---