The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include <stdio.h>
int main(int argc, char* argv[])
{
int n, i, j;
int adj[10];
int num[10][11];
scanf("%d", &n);
for(i = 1; i < n; ++i)
scanf("%d", &adj[i]);
for(i = 0; i < 10; ++i)
num[i][n] = 1;
for(j = n-1; j; --j)
{
for(i = 0; i < 10; ++i)
{
num[i][j] = 0;
if ((i - adj[j]) >= 0) num[i][j] = num[i-
adj[j]][j+1];
if (adj[j] && ((i + adj[j]) < 10)) num[i][j] +=
num[i+adj[j]][j+1];
}
}
j = 0;
for(i = 1; i < 10; ++i)
j += num[i][1];
printf("%d\n", j);
return 0;
}
On Dec 12, 11:31 am, KAY <[email protected]> wrote:
> If for a number n digits long, the absolute difference between
> adjacent digits is given, how to find out the number of different
> numbers with these absolute differences ?
>
> for eg,
> if n=5
> and the absolute differences are
> 3 2 5 1
> then 1 possible number is
> 6 3 5 0 1 (because |6-3|=3,|3-5|=2 and so on...)
>
> How many such numbers will be there?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
