How to solve this problem using P&C -Link

Problem: Count of N-digit numbers in base K with no two consecutive zeroes

My idea: Suppose we consider N digit as _ _ _ _ ~ N digits. Since no leading 0 is allowed, the first place can be filled with a total of (k-1) ways. The second place can be filled with a total of k ways, since we can consider 0. Similarly for third position, we can fill by k-1 ways.

But this fails for many cases. How to do this?

@galencolin @ssjgz

Where can I test my solution for this problem ?

I am not sure, if any other platform has a similar type of problem. It was just a sudden thought while doing this. But you can try matching the solution of the given methods with different inputs.

Your logic is wrong. What if you donâ€™t fill the second place with a 0?

I think he did consider that part. Can you explain it in detail ?

Yes, I am doing considering two different conditions, one for even places and one for odd places.

For odd-

- Let x=(n+1)/2. So, (k-1) occurs odd times with a frequency of x and even with frequency n-x . So total= (k-1) ^ (x) * k^(n-x). Similarlt for odd too. But this doesnâ€™t seem right.

My idea:

Consider an N digit number. Letâ€™s assume N = 4 for simplicity.

The number is now _ _ _ _.

You can fill the first place in total of K-1 ways.

We have 3 digits to be filled. The numbers we wat to exclude are X00Y and XY00. The number of ways you can pick two consecutive 0s in a string of length n is n-1.

We need to exclude these cases.

If Iâ€™m not wrong, the answer is (K-1)(K^{N-1}-K^{N-3}).

EDIT: Let me elaborate.

The number of ways you can get any number will be (K-1)(K)^{N-1} (this is basic).

The number of ways you can get a number like that with 2 consecutive zeroes will be:

First digit: (K-1) ways because trailing zeroes arenâ€™t allowed.

Remaining digits: We can choose 2 consecutive zeroes in N-2 ways from N-1 digits. We have N-3 places left to fill. These can be any digit assuming that we have already picked 2 consecutive 0s. So we can fill them in K^{N-3} ways.

Therefore the answer is (K-1)(K^{N-1}-{K}^{N-3}) ways.

Please let me know if Iâ€™ve done anything wrong because Iâ€™m bad at combinatorics

This makes sense. Can you please explain, why K^(n-3)

Iâ€™ve edited the comment.

This is a nice methodâśŚ. Thank you for thisđź™‚

Shouldnt you multiply K^(n-3) by (n-2) ?

Since there are N-2 ways to choose 2 consi zeros.â€™

Final answer :

(k-1) * ( k^(n-1) - (n-2)*( k^(n-3) ) )

No. Because we have K^{N-3} ways to fill N-3 digits. What does this mean? It simply means that weâ€™ve already filled 3 digits, right? Now what are those 3 digits? One of them is the non-zero last digit. The other 2 are the consecutive 0s. Did you understand?

Are you sure it will be consecutive ?

I think cases like this will also be counted where zeros are not consecutive.

[ 1 , 2 3 0 5 0 7 ]

No, youâ€™re slightly confused. In combinatorics, we donâ€™t care about the numbers themselves. We only care about â€śhow many numbers are there such that blah blah blahâ€ť. And just to prove to you that Iâ€™m right, Iâ€™ve written a python program which gives the right output for N, \ K = 3, \ 10 (3 digit numbers in base-10).

```
from math import pow
arr = list(map(int, input().split(' ')))
print(int((arr[1]-1)*(pow(arr[1], arr[0]-1)-pow(arr[1], arr[0]-3))))
```

My code and the GFG sample test case give 891.

Actually Iâ€™ve tried this code for different inputs, and it doesnt work. Thats why I was asking.

It wonâ€™t work for special cases where N \leq 2 because we have N-3 in the exponent. But the answer is (K-1)K when N =2 and K-1 for N = 1 because we canâ€™t have a 0 in last digit.

Can you please tell what inputs youâ€™re talking about?

I am pretty sure somethings wrong, please run this code to see your method and dp:

https://ide.geeksforgeeks.org/6Bscpn4vzR

What was the input?

Itâ€™s giving WA for almost every input. Did you check ?