Arrays, strings and recursion

A reference number too long to add

Every invoice in a payments system gets a reference number: a 22-digit string, issued in order, so each new one is the last one plus 1. For one large merchant, the service that issues these numbers has started to crash.

The line that fails converts the reference string into a long, adds 1, and converts the result back to a string. A Java long stops at 9,223,372,036,854,775,807, which is nineteen digits. The merchant's latest reference is 4100000000000000099999, which is twenty-two. The number does not fit, so parseLong throws an exception before any adding happens.

So the fix has to work on the digits one at a time, the way you add on paper: start with the rightmost digit, and when a digit would go past 9, write 0 and carry 1 to the digit on its left. The loop is quick to write. Now look at the reference again. It ends in three 9s, and no test in the suite has ever used a number ending in 9. Sooner or later a reference will be made entirely of 9s. Before reading on, run the loop on 999 in your head.

Pause and predict You add 1 to 999, one digit at a time from the right. Each 9 becomes 0 and passes a carry of 1 to the digit on its left. After the loop has handled all three digits, what is the situation?

Say what the loop knows

Easy problems usually go wrong in one of three places: the first step, the last step, or a step where something carries over from one position to the next. You can avoid most of these mistakes by writing one sentence before you write the loop. The sentence answers the question what is true each time the loop is about to handle the next position? That sentence is called the loop's invariant.

Take Plus One. The number 499 is stored as the array [4, 9, 9], one digit per slot, and you must add 1 to it. Addition on paper starts at the last digit, so the loop walks from the end of the array towards the front. The index i is the position the loop is looking at.

Here is why that sentence makes the code correct. At the start, i is the last position, there are no digits to its right, and the 1 you were asked to add has not been added yet. So the sentence is true before the first step.

Now look at one step. If the digit at i is less than 9, adding 1 to it gives another single digit, so no carry is produced and no digit to the left changes. The number is complete and the loop can return. If the digit is 9, adding 1 gives 10, so you write 0 in this position, which is now final, and the carry of 1 moves to position i - 1. The sentence is true again one position further left. If the loop moves past the first digit, the carry still has not been added, which only happens when every digit was 9, so the answer is a 1 followed by zeros.

Pause and predict Merge Sorted Array gives you two sorted arrays. nums1 holds its values at the front and has empty slots at its end, exactly enough to hold nums2. You must merge nums2 into nums1 without another array. Should the loop fill nums1 starting from the front (smallest values first) or from the back (largest values first)?

Recursion: trust the smaller call

Some answers are defined in terms of a smaller answer. In Count and Say, term n is what you get by reading term n - 1 aloud: 21 is read as "one 2, one 1", which gives 1211. To write a recursive function for this, do not trace the calls all the way down to term 1. Assume that countAndSay(n - 1) returns the right string, write the one step that turns that string into term n, and return the smallest case, term 1, directly.

Pause and predict Term 4 of Count and Say is 1211. Trusting it, what is term 5?

This is a proof by induction written as code: the smallest case is correct, and each step is correct whenever the smaller call is correct. Two things can break it. The first is a missing base case, so the calls never stop. The second is depth: every call that has not returned yet keeps its memory on the call stack, and Python raises an error after about 1,000 nested calls. Recursion is fine for a depth of 30, but a depth of 100,000 needs a loop. Unit 0 works out how much memory those waiting calls use.

How to recognise it

Pause and predict Two of these problems can be solved with one loop and no extra memory beyond a few variables. Which one cannot?

Three that only look like it

• If you must find a pair quickly in unsorted data, comparing every value with every other value is O(n²). Storing the values already seen in a map makes it one pass. That is hashing.
• If two indices move through sorted data and each step rules out values that cannot be part of the answer, the correctness rests on an argument about which values are safe to skip. That is two pointers. Reverse String and Merge Sorted Array are its simplest cases.
• If the digits are in base 2, the carry logic is done with the bit operations XOR and AND. That is bits and maths.

Where it bites

Pause and predict Plus One allows up to 100 digits. Why not convert the digits into a single number, add 1, and split the result back into digits?

• Converting the digits to a number. A long holds 18 digits safely, but Plus One allows 100 digits and Multiply Strings allows 200. Work on the digits directly.
• Walking in the wrong direction. A carry moves from the last digit towards the first, so the loop must start at the end. When you merge into an array that has free space, write into the free space first.
• Reading past the end of an array. Roman to Integer looks at the next symbol, and Longest Common Prefix reads position i of every word. Check that the index exists before you read it.
• Recursion without a base case, or too deep. Without a base case the calls never stop. With a base case but a large depth, the call stack runs out of space. Count and Say goes 30 calls deep, which is fine; a recursive Reverse String on 100,000 characters would go 50,000 deep, which is not.