[Facebook] 66. Plus One

leetcode.com/problems/plus-one/

Plus One - LeetCode

 

Given a non-empty array of 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 1:

Input: digits = [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.

Example 2:

Input: digits = [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.

Example 3:

Input: digits = [0] Output: [1]

 

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

음이 아닌 정수를 나타내는 비어 있지 않은 숫자 배열이 주어지면 정수로 1을 증가시킵니다.

숫자는 최상위 숫자가 목록의 맨 위에 있고 배열의 각 요소에 단일 숫자가 포함되도록 저장됩니다.

숫자 0 자체를 제외하고 정수에 선행 0이 포함되어 있지 않다고 가정 할 수 있습니다.



예 1 :

입력 : 숫자 = [1,2,3] 출력 : [1,2,4] 설명 : 배열은 정수 123을 나타냅니다.

예 2 :

입력 : 숫자 = [4,3,2,1] 출력 : [4,3,2,2] 설명 : 배열은 정수 4321을 나타냅니다.

예 3 :

입력 : 숫자 = [0] 출력 : [1]



제약 :

1 <= 자릿수 길이 <= 100
0 <= 숫자 [i] <= 9

 

 

---

Solution

---

Overview

"Plus One" is a subset of the problem set "Add Number", which shares the same solution pattern.

All these problems could be solved in linear time, and the question here is how to solve it without using the addition operation or how to solve it in constant space complexity.

The choice of algorithm should be based on the format of input. Here we list a few examples:

1. Integers

   Usually the addition operation is not allowed for such a case. Use Bit Manipulation Approach. Here is an example: Add Binary.

2. Strings

   Use bit by bit computation. Note, sometimes it might not be feasible to come up a solution with the constant space for languages with immutable strings, e.g. for Java and Python. Here is an example: Add Binary.

3. Linked Lists

   Sentinel Head + Schoolbook Addition with Carry. Here is an example: Plus One Linked List.

4. Arrays (also the current problem)

   Schoolbook addition with carry.

Note that, a straightforward idea to convert everything into integers and then apply the addition could be risky, especially for the implementation in Java, due to the potential integer overflow issue.

As one can imagine, once the array gets long, the result of conversion cannot fit into the data type of Integer, or Long, or even BigInteger.

---

Approach 1: Schoolbook Addition with Carry

Intuition

Let us identify the rightmost digit which is not equal to nine and increase that digit by one. All the following consecutive digits of nine should be set to zero.

Here is the simplest use case which works fine.

Here is a slightly complicated case which still passes.

And here is the case which breaks everything, because all the digits are nines.

In this case, we need to set all nines to zero and append 1 to the left side of the array.

Algorithm

• Move along the input array starting from the end of array.

• Set all the nines at the end of array to zero.

• If we meet a not-nine digit, we would increase it by one. The job is done - return digits.

• We're here because all the digits were equal to nine. Now they have all been set to zero. We then append the digit 1 in front of the other digits and return the result.

Implementation

 

 

1 / 7

Complexity Analysis

• Time complexity : \mathcal{O}(N)O(N) since it's not more than one pass along the input list.

• Space complexity : \mathcal{O}(1)O(1) when digits contains at least one not-nine digit, and \mathcal{O}(N)O(N) otherwise.

 

 

 

 

해결책
개요
"Plus One"은 동일한 솔루션 패턴을 공유하는 문제 세트 "Add Number"의 하위 집합입니다.

이러한 모든 문제는 선형 시간으로 해결 될 수 있으며 여기서 문제는 덧셈 연산을 사용하지 않고 해결하는 방법 또는 일정한 공간 복잡성으로 해결하는 방법입니다.

알고리즘 선택은 입력 형식을 기반으로해야합니다. 다음은 몇 가지 예입니다.

정수

일반적으로 이러한 경우 추가 작업이 허용되지 않습니다. 비트 조작 접근법을 사용하십시오. 여기에 예가 있습니다 : 바이너리 추가.

문자열

비트 단위 계산을 사용하십시오. 때때로 불변의 문자열을 가진 언어에 대한 상수 공간을 가진 해결책을 찾는 것이 불가능할 수도 있습니다. Java 및 Python 용. 예를 들면 다음과 같습니다. 바이너리 추가.

연결된 목록

Sentinel Head + Schoolbook Addition with Carry. 예를 들면 다음과 같습니다. Plus One Linked List.

배열 (현재 문제이기도 함)

캐리와 교과서 추가.

모든 것을 정수로 변환 한 다음 추가를 적용하는 간단한 아이디어는 잠재적 인 정수 오버플로 문제로 인해 특히 Java 구현의 경우 위험 할 수 있습니다.

상상할 수 있듯이 배열이 길어지면 변환 결과가 Integer, Long 또는 BigInteger의 데이터 유형에 맞지 않습니다.



접근 방식 1 : 캐리를 사용한 교과서 추가
직관

9와 같지 않은 가장 오른쪽 숫자를 식별하고 그 숫자를 1 씩 늘립니다. 연속되는 9 자리는 모두 0으로 설정해야합니다.

다음은 잘 작동하는 가장 간단한 사용 사례입니다.

단순한

여전히 통과하는 약간 복잡한 경우가 있습니다.

더

그리고 모든 숫자가 9이기 때문에 모든 것을 깨뜨리는 경우가 있습니다.

핸들

이 경우 9를 모두 0으로 설정하고 배열의 왼쪽에 1을 추가해야합니다.

추가

연산

배열의 끝에서 시작하여 입력 배열을 따라 이동합니다.

배열 끝에있는 모든 9를 0으로 설정합니다.

9 자리가 아닌 숫자를 만나면 1 씩 늘립니다. 작업이 완료되었습니다-숫자를 반환하십시오.

모든 숫자가 9와 같기 때문에 여기에 있습니다. 이제 그들은 모두 0으로 설정되었습니다. 그런 다음 다른 숫자 앞에 숫자 1을 추가하고 결과를 반환합니다.

이행

흐름
1/7

복잡성 분석

시간 복잡도 : \ mathcal {O} (N) O (N) 입력 목록을 따라 두 번 이상 통과하지 않기 때문입니다.

공간 복잡도 : 숫자에 9 자리가 아닌 숫자가 하나 이상 있으면 \ mathcal {O} (1) O (1), 그렇지 않으면 \ mathcal {O} (N) O (N).