You’re right. What went wrong? And why do the samples work?
1 Like
It works for n=3 only.
I cwont be able to sleep if I dont solve this problem 
What complexity are you looking for?
1 Like
Me too. @galencolin, please check my formula and let me know what’s wrong. I don’t know where I went wrong.
1 Like
Your idea is wrong. First, you have to account for the n - 2 possible positions for the pair of zeros. And also, you aren’t counting strings that have more than one consecutive pair of zeros.
That means there’s no quick fix you can do to correct it, as it’s more complex than your formula would be
2 Likes
If we have atleast one consecutive pair of zero, then all other n-3 position can have any digit including zero.
Wont this include that case ?
1 Like
Thanks. Is a solution with combinatorics even possible?
(As an example,) take n = 4. You’ll count both strings of the form x00 and 00y, right? But if x = y = 0, you’ll count the string 000 twice. This effect is magnified as n grows.
2 Likes
okay, I think it might overcount…
Not sure, thinking about it myself, but I’m also weak in combo
2 Likes
Even if there’s a combo solution, it’s very likely that there isn’t one with asymptotics better than O(n), because you can represent the answer in the form \sum\limits_{i = 0}^{n}{c_i \cdot (k - 1)^{n - i}}, where c_i is the count of n-digit numbers with exactly i zeros. In all my life I’ve never seen a way to optimize a formula like this.
2 Likes
@galencolin By combinatorics, the formula comes out to be 
Now using wolfram alpha we get-Link or Link
2 Likes
Can you explain ?
Yes
Even after convincing myself of that identity’s correctness in the past, I still don’t understand it lol
If you go through this link-
Link
and put value of n and k, in your program the output you get is the same you get from this formula. This means I have deduced a correct formula. Now Explanation-
Consider Cases as numbers formed using 0 zeroes, numbers formed using 1 zeroes, numbers formed with using 2 zeroes and so on.
No. of Numbers formed without any zero= k^(n-1)
No. of Numbers formed with 1 zero =(n-1)C1*(k-1)^(n-1)
No. of Numbers formed with 2 zeroes =(n-2)C2*(k-1)^(n-2)
…
General term= (n-i)Ci*(k-1)^(n-i)
The reason it works is, when you decide you’re going to put down i zeros, each zero immediately invalidates another position to the right of it (except you don’t care about the last one). So you really only have n - i + 1 positions to put the i zeros down (which becomes n - i because you also can’t put a zero at the first position)
Another way to think about it: in reverse. Say you put i zeros on a strip of n - i numbers. Then, at each position where you have a zero except for the last one, insert a nonzero digit directly to the right of it. You’ll get a string of length n with no pair of consecutive zeros, and each initial string will be unique.
1 Like
I didn’t expect my simple question to become this tough😐
1 Like
I am glad it did :]
4 Likes
Consider the case when we have 3 zeroes in the number,
The first digit can’t be zero (otherwise the number of digits will become (n-1). So there are (k-1) options to fill the first digit.
Now we are left with (n-1) digits, out of which 3 are zero.
Number of digits except zero=(n-1-3)=(n-4). Now using the gap method of combinatorics (to find the number of ways we can allot zeroes such that no two of them are consecutive).
Number of gaps in (n-4) digits=(n-4+1), each of them can be filled with a zero.
=>
Ways to fill zeroes=(n-4+1)C3
Ways to fill the first digit= (k-1)^(n-1)
Ways to fill the rest (n-4) digits=(k-1)^(n-4)
Total number of ways=(n-4+1)C3 * ((k-1)^(n-1)) * ((k-1)^(n-4))=(n-3)C3 * (k-1)^(n-3)
in general, =(n-i)Ci * (k-1)^(n-i)
2 Likes