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
2 Likes
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
2 Likes
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🙂
1 Like
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?
2 Likes
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:
What was the input?
It’s giving WA for almost every input. Did you check ?