0
$\begingroup$

I came across this interesting problem in a test and I couldn't complete it.

There is a string given s which can consists of numbers between 0-9 and '?'. In place of '?' we can insert any of the numbers between 0 to 9. We need to find the number of ways in which it can be done so that no two adjacent numbers are same.

For e.g: ?2 should return 9 as there are 9 ways to do this. 02 12 32 42 52 62 72 82 92

???should give 810

I tried naive brute force approach like creating conditions based on the position of? but that took me nowhere.

So thought maybe it could be solved recursively. But unable to form a logic.

I'd appreciate to know the intuition behind solving this problem. I can do the implementation.

$\endgroup$
3
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W.
    Mar 13 at 16:57
  • $\begingroup$ So the first numner can be from 0-9 so total 10 numbers are possible, the next number should exclude the one that comes just before it so total 9 numbers are possible at this. Similarly for the last one any of the numbers come that are not there at the second pos. So total 10*9*9 = 810 $\endgroup$
    – ABGR
    Mar 13 at 19:41
  • $\begingroup$ The calculations will be similar to those for the chromatic polynomial for the path/cycle graph. see here $\endgroup$
    – codeR
    Mar 14 at 6:05

1 Answer 1

1
$\begingroup$

If you try to use recursion naively, you'll attempt to solve the problem for $w a$, where $w$ is a string and $a$ is a character (the possible characters being $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ?\}$). This will fail, since the number of possibilities for $w a$ depends not only on the number of possibilities for $w$, but also on the last letter of $w$, because that influences the possibilities for filling $a$ if it happens to be a "?".

Slightly less naively, you can do a bit of dynamic programming. Assume you have a table of the number of possibilities for filling $w$ assuming that if the last letter of $w$ is a "?" then it must be filled with $i$, for $i = 0, …, 9$. Try to build the same table for $w a$. Try to bootstrap the process for the empty string, and at the end, when you're done for the whole string, you should be able to sum the values in the table to get the result.

And slightly less naively than that, you can

  • Identify runs of consecutive "?",
  • Remark that the total number of possibilities is the product of the numbers of possibilities for each run, since they are "independent" (assuming that there not already two adjacent identical digits in the input string),
  • Compute the number of possibilities for a run $d_1 ???…??? d_2$, where $d_1, d_2$ are digits and there are $n$ times "?" in the middle (don't forget to special case runs of "?" at the beginning or at the end; another hint: distinguish the cases $d_1 = d_2$ and $d_1 ≠ d_2$),
  • Conclude.
$\endgroup$
2
  • $\begingroup$ Can you please explain the sub problem underlying within this problem and possible recurrence relation? Want to solve using top down approach $\endgroup$
    – ABGR
    Mar 13 at 19:42
  • 1
    $\begingroup$ Check out the calculations for chromatic polynomials of path and cycle graphs. Based on the above answer, a similar polynomial (closed form expression) can be derived. Thus, there is no need for dynamic programming or such heavy calculations. $\endgroup$
    – codeR
    Mar 14 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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