CODEWITHSUNDEEP
calgorithmrecursiondynamic-programming
noman pouigt
noman pouigt

Reputation: 976

Any other solution for recursive solution

I was trying to find how many numbers of length n are there such that each number is at least 4 smaller/greater than the number before and after it. Eg: if n = 5, such numbers are 39518, 15951, etc.

Below is the solution, i could come up with: It is taking a long amount of time even for input size as low as 1000.I am sure, there are some better approaches to solve this problem. I would appreciate if someone can give some 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;
    for (i=0;i<=9;i++) {
        if (pos_to_fil == 0 && i == 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;
}

Upvotes: 2

Views: 216

Answers (2)

Stef
Stef

Reputation: 658

Short answer: don't use recursion, go bottom up and use dynamic programming.

Longer answer: Basically you're iterating over all possible solutions. The only statement that increases count is the count++ and because we have to go up to a number with over 600 digits that's going to take a while. (Even if it wouldn't take a function call for every count++)

So somehow we need to increase count with a whole lot more then just 1 at the time. How to do that?

Suppose we already know the answer to n=2 is 36 possibilities. Does that help us to compute how many possibilities there are for n=3? No. Not really, because we don't know what those 36 numbers are. One of those two-digit numbers is 15 which could be extended to 150, 151 and 159 (3 possibilities). Another two-digit number is 30 which could be extended to 304, 305, 306, 307, 308 and 309 (6 possibilities). We clearly can't just multiply 36 with some constant factor to arrive at the solution for n=3.

But there is a pattern nonetheless. The fact that 30 spawns 6 new numbers for the next generation implies that 40, 50, 60 and all other two-digit numbers that end on a 0 will also spawn 6 new numbers. 15 spawns 3 new numbers, and so will all other numbers that end on a 5.

So what if we do start by computing n=2, and in stead of remembering all 36 numbers, we remember this array: [6, 5, 4, 3, 2, 2, 2, 3, 4, 5]. This array implies we don't know exactly what those 36 numbers are, but 6 of them end on a 0, 5 of them end on a 1, 4 on a 2 and so on.

Now we can compute the same array for n=3 by doing some additions. 0 can be spawned from a 4, 5, 6, 7, 8 or 9. Adding them all up implies that for n=3 there will be 2 + 2 + 2 + 3 + 4 + 5 = 18 numbers that end on a 0. The entire array for n=3 is [18, 16, 14, 12, 15, 16, 15, 18, 20, 22]

Unfortunately I don't speak c but here is a 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;                                        

        for (int i = 1; i < n; i++) {                                       
            for (int nextDigit = 0; nextDigit < 10; nextDigit++) {          
                next[nextDigit] = BigInteger.ZERO;                          
                for (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;                                   
        for (BigInteger i : counts) sum = sum.add  (i);                     
        return sum;                                                         
    }                                                                       

}

It has two arrays: counts for the array of the current generation (n=2 in the example above) and next for the next generation (n=3 in the example). When the algorithm is done computing next it swaps the two arrays, implying we'll use the next from this generation as a current for the next generation.

It has 3 for loops. The outer loop simply counts generations and isn't used at all. The nextDigit counts the digits in the next generation, while digit counts the digit in the current generation. When they're at least 4 apart we do the addition.

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

58671138329570171371420484902268532315073277852051653969830525802838628724212731137694290047005040297045274423072752812252866695216074181116219893270512906481125049825987756071510466880415373048496191391932743103313044071304405218219902707133109687674960299002863298632965964118240544824530569540542700793488917467060307664191744432111922492168260259079355618958225678548171234101375097873342091776899282686824362584042717489292059166512255400959907373002265039739675037774831081921743873154470907306563401667845616259033848968890244196752759640923743592116170624821165172596009768024780906078208584276112384909371479169927564723938874400811048288 possibilities.

Upvotes: 4

maskacovnik
maskacovnik

Reputation: 3084

Maybe you can rewrite the for header to make it shorter using two for cycles:

int previous = out[pos_to_fill-1];
int i;
//lower than 4
for (i=0;i<previous-4;i++) {
    //... for cycle body
}
//higher than 4
for (i=previous+4;i<=9;i++) {
    //... for cycle body (the same)
}

To not repeat cycle body, I would put body to function if it wont have many parameters

Note: not tested, starting i values and conditions can be bad, this is only an idea

Upvotes: 0

Related Questions