I am overcounting...not sure where..help?

Posted by

Gokul 14 Jan 2013 18:37

Hi,

I am just beginning to write code although i am bit familiar with algorithms and datastructures.

I wrote this solution. But its wrong. I kinda feel that i am overcounting but not sure where it is.

if( n == 0) return 1;

if(n == 1) return k-1;

return k-1 * ( k * f(n-2,k) + k * k-1 * f(n-3,k) )

if digit n-1 can have zero there are k ways we can fill it, hence k * f(n-2,k)

else if digit n-1 cannot have zero then we can use k-1 ways for digit n-1 and k ways for n-2.

*Edited by author 14.01.2013 18:41*