Plus One

Easy

The problem

digits holds the digits of a non-negative whole number, most significant digit first (so [1, 2, 3] means 123). Add one to the number and return its digits in the same format.

Example 1
Input: digits = [1, 2, 3]
Output: [1, 2, 4]
Example 2
Input: digits = [4, 3, 2, 9]
Output: [4, 3, 3, 0]
4329 + 1 = 4330.
Example 3
Input: digits = [9, 9]
Output: [1, 0, 0]
99 + 1 = 100 needs an extra digit.

Limits

1 ≤ len(digits) ≤ 100
0 ≤ digits[i] ≤ 9
No leading zeros, except for the number 0 itself

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Start from the last digit. When does the carry stop?

The idea

Walk from the end: a digit < 9 gets +1 and you are done; 9s become 0; if everything was 9 prepend a 1.

Target: O(n) time

Go function shape

func plusOne(digits []int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// PlusOne: add one to a number stored as a digit slice.
func PlusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] < 9 {
			digits[i]++
			return digits // no carry left to pass on
		}
		digits[i] = 0 // 9 + 1 = 0, carry one position left
	}
	return append([]int{1}, digits...) // all nines: 999 -> 1000
}

Read the lesson: Bit Manipulation & Math