0
$\begingroup$

Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in the integer is at most $m$?

The integer cannot start with a $0$. All digits from $0$ to $n-1$ must be present.

Example: for $n = 3$ and $m = 6$ there are $18$ such numbers ($210, 2101, 21012, 210121 \ldots$)

I know there is a dynamic programming method to solve this. After looking the solution, I am not able to understand it. Can anybody please give any good solution to me?

$\endgroup$
  • 1
    $\begingroup$ You should present the solution you have at hand and describe your specific problems -- then we can really help you. $\endgroup$ – Raphael Aug 29 '13 at 13:28
  • $\begingroup$ I had the recursion at my hand. But I could not figure out the parameters and what the table was calculating and how. This is something like this: f(S, d, l) = f(S|1<<d+1, d+1, l+1) + f(S|<<d-1, d-1, l+1). But, now, everything is clear from Yuval's answer. $\endgroup$ – Rahul Sharma Aug 29 '13 at 15:50
  • $\begingroup$ Good thing it matches, then; without insider knowledge Yuval may be talking about a whole other recurrence. That is to say, please include such detail in future questions you post. $\endgroup$ – Raphael Aug 30 '13 at 11:05
0
$\begingroup$

Hint: The table consists of cells $T(S,d,\ell)$, which count numbers of length $\ell$ in which the last digit is $d$ and the set of digits is $S$. Unfortunately this solution is exponential in $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.