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 ((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 <amulya.manches...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.