Dynamic Programming – CrazyNumbers

Problem Statement

We are interested in finding the count of all N digit crazy numbers. Let us define a crazy number. A crazy number is a number where the magnitude of its consecutive digits differ by 1.

For e.g.: Here is a list of all 2 digit crazy numbers:

crazynunmbers

The total number of 2 digit crazy numbers is 17. You can notice that in all the numbers the digits differ only by 1.

Similarly for three digit numbers the count reaches 32. For four digit numbers it becomes 61 and very soon it increases exponentially to 924903595810 for a 40 digit number.

It might look like the a problem which takes exponential running time. But we will try to solve it in linear time.

Approach

Closely observing the problem shows that we can use dynamic programming to solve this.

Why?

Here are few points to justify my claim of using dynamic programming

crazynunmbers1

  • The above image shows that every three digit crazy number is derived from a two digit crazy number by adding a third digit.
  • The third digit can be either 1 greater than the last digit or 1 lesser than the last digit of the two digit number.
  • This means each two digit crazy number will derive exactly 2 three digit numbers.
  • However, the two digit number ending in 9 will only result in one three digit number.
  • Also, the two digit number ending in 0 will produce only one three digit number.

The above explanation shows that the bigger problem can be decomposed into smaller problem and the solution can be incrementally built.

Solution

Let us write down the count of possible crazy numbers ending in each of the digits (0 through 9)

Looking at the above images we know the following:

crazynumber3

Only 1 two digit crazy number ends with zero. (10)

Only 1 two digit crazy number ends with one. (21)

2 two digit crazy numbers ends with two. (12, 32) and so on…

 

And as we discussed each of the two digit crazy number will generate two numbers one ending with a higher digit and other ending with a lower digit.

Means the number ending in 1 will generate a number ending in 0 and other number ending in 2. The third row in the above image shows that there is only one three digit number ending in 0, which is contributed by the second column in the second row.

Similarly the three digit number ending with 1 is contributed by the two digit number ending in zero and the two digit number ending in 2 in the second row. The sum is 3.

The sum of the ith row will give you the total count of all i digit crazy numbers.

This gives our dynamic programming relation. Which means you can build a table for N rows and then its iteration over a given row to find the count.

Here is the DP table for the solution.
crazynumber4

How to read this table?

  • The table index starts from 0, 0.
  • The numbers in the zeroth rows are the ending digits of a number.
  • The zeroth column is to represent one particular case, for e.g.  row 1 deals with 2 digit numbers, row 3 deals with 3 digit numbers and so on.
  • Column 1 and 12 are dummy columns  which are required to run the algorithm without specifically coding for the boundary cases.
  • Column 13 gives the count of all crazy numbers possible with the corresponding number of digits.
  • The value of the cell at the intersection of row header 5 and column header 4 is the count of all five digit crazy numbers ending in 4.

Source Code

You can see that I have initialized the row 1 with count of two digit numbers . You can choose to do it differently by initializing it with one digit numbers, but I think there cannot be any crazy number with one digit :).

Analysis

The space required is proportion to N where N is the max digits. Hence the space complexity is O(N). We will not take into account the columns because the columns are fixed and would not depend upon the value of N.

The running time is linear as well, its basically populating each row and summing up the columns, O(N).

  • Mond Wan

    Example code line:9 should be A[i][0] = 0; instead of A[i][1] = 0;?

    • thanks for pointing that out.. I really appreciate that 🙂

  • Anwar Ahmed

    this is brilliant explanation.