c - Any other solution for recursive solution -

i trying find how many numbers of length n there such each number @ least 4 smaller/greater number before , after it. eg: if n = 5, such numbers 39518, 15951, etc.

below solution, come with: taking long amount of time input size low 1000.i sure, there better approaches solve problem. appreciate if can give pointers.

#include <stdio.h>  int out[100000]; int count; void foo(int *out, int pos_to_fil, int size) {     if (pos_to_fil == size) {         count++;         return;     }     int i;     (i=0;i<=9;i++) {         if (pos_to_fil == 0 && == 0)             continue;         if (pos_to_fil >0 && abs(out[pos_to_fil-1] -i) < 4)             continue;         out[pos_to_fil] = i;         foo(out, pos_to_fil + 1, size);     } }  int main(void) {     foo(out, 0, 1000);     printf("count %d\n", count);     return 0; } 

short answer: don't use recursion, go bottom , use dynamic programming.

longer answer: you're iterating on possible solutions. statement increases count count++ , because have go number on 600 digits that's going take while. (even if wouldn't take function call every count++)

so somehow need increase count whole lot more 1 @ time. how that?

suppose know answer n=2 36 possibilities. compute how many possibilities there n=3? no. not really, because don't know 36 numbers are. 1 of two-digit numbers 15 extended 150, 151 , 159 (3 possibilities). two-digit number 30 extended 304, 305, 306, 307, 308 , 309 (6 possibilities). can't multiply 36 constant factor arrive @ solution n=3.

but there pattern nonetheless. fact 30 spawns 6 new numbers next generation implies 40, 50, 60 , other two-digit numbers end on 0 spawn 6 new numbers. 15 spawns 3 new numbers, , other numbers end on 5.

so if start computing n=2, , in stead of remembering 36 numbers, remember array: [6, 5, 4, 3, 2, 2, 2, 3, 4, 5]. array implies don't know 36 numbers are, 6 of them end on 0, 5 of them end on 1, 4 on 2 , on.

now can compute same array n=3 doing additions. 0 can spawned 4, 5, 6, 7, 8 or 9. adding them implies n=3 there 2 + 2 + 2 + 3 + 4 + 5 = 18 numbers end on 0. entire array n=3 [18, 16, 14, 12, 15, 16, 15, 18, 20, 22]

unfortunately don't speak c here solution in java.

import java.util.*;                                                          import java.math.*;                                                           class bignum {                                                                     public static void main (string[] a) {                                           scanner in = new scanner (system.in);                                        system.out.println (new bignum().solve(in.nextint()));                   }                                                                              biginteger solve(int n) {                                                        if (n == 0) return biginteger.zero;                                          biginteger[] counts = new biginteger[10];                                    biginteger[] next = new biginteger[10];                                      biginteger[] temp;                                                           arrays.fill (counts, biginteger.one);                                        counts[0] = biginteger.zero;                                                  (int = 1; < n; i++) {                                                    (int nextdigit = 0; nextdigit < 10; nextdigit++) {                           next[nextdigit] = biginteger.zero;                                           (int digit = 0; digit < 10; digit++) {                                       if (math.abs (digit - nextdigit) >= 4) {                                         next[nextdigit] = next[nextdigit].add (counts[digit]);                     }                                                                        }                                                                        }                                                                            temp = counts;                                                               counts = next;                                                               next = temp;                                                             }                                                                             biginteger sum = biginteger.zero;                                            (biginteger : counts) sum = sum.add  (i);                              return sum;                                                              }                                                                         } 

it has 2 arrays: counts array of current generation (n=2 in example above) , next next generation (n=3 in example). when algorithm done computing next swaps 2 arrays, implying we'll use next generation current next generation.

it has 3 loops. outer loop counts generations , isn't used @ all. nextdigit counts digits in next generation, while digit counts digit in current generation. when they're @ least 4 apart addition.

and in case you're wondering, result n=1000 indeed quite big, , took me 165 milliseconds compute:

58671138329570171371420484902268532315073277852051653969830525802838628724212731137694290047005040297045274423072752812252866695216074181116219893270512906481125049825987756071510466880415373048496191391932743103313044071304405218219902707133109687674960299002863298632965964118240544824530569540542700793488917467060307664191744432111922492168260259079355618958225678548171234101375097873342091776899282686824362584042717489292059166512255400959907373002265039739675037774831081921743873154470907306563401667845616259033848968890244196752759640923743592116170624821165172596009768024780906078208584276112384909371479169927564723938874400811048288 possibilities.