DP is one of the most important trick used in programming. This article discusses about a variant that can be used to solve problems like how many numbers are there between \(a\) and \(b\) such that they contain a digit \(x\). Now since this one may be easy and you can think of some formula but DP can be used as a very nice approach here.
Suppose you have been given a number \(1608\) and you want to enumerate all the numbers which are lesser than or equal to it. This can be done easily using the following process.
Let us assume we have four blanks \( ___ ___ ___ ___\) . Now what can be the first digit from left it can be either \(1\) or \(0\). i.e.
\(0 ___ ___ ___\) and \(1 ___ ___ ___\) . Now if we have placed \(0\) in the beginning it is a clear observation that we have not made any \(4\) digit number so the second digit can take values \(0\) to \(9\), but if we have placed \(1\) there then the next digit will be always \(0\) to \(6\) or else number will be greater than the required number.
In digit DP whenever we form all numbers smaller than or equal to any number we start formation with the most significant bit. Then Suppose total digits in the number is to be atmost \(4\) (like here) then we try to place each digit \(0-9\) in all the \(4\) places but keeping in mind that the number formed is always lesser than or equal to the limiting number.
I prefer recursion to be the best way to solve it and we can easily memoize it.
In recursion we always record with us the following things --
Read the above points carefully to understand the recursion properly.
To understand we can take solve some problems in difficulty order.
Problem - 1 : Count \(3\) digit numbers containing digit \(7\)
Solution - : You can start enumerating numbers. For explanation I will use the code below.
For the first digit from right you have \(9\) choices \(1\) to \(9\). For second \(10\) choices and for third \(10\) choices. Suppose you are making a choice of second digit then if the first digit from whose recursion you jumped into this one is already \(7\) then value of contains will be true or else if you have not placed \(7\) till now then contains will be false and will become true when you will call function count by placing digit as \(7\).
When recursive programs are called then there has to be some condition where we have to stop them. So here you need to recurse until you reach a length greater than maximum length (which is \(3\) ).
Its clear that this recursion with itself stores information as position and contains.Now suppose you reach the end condition with contains as true, its like :
\(1\) \(7\) \(9\) contains digit \(7\) so return \(1\) because this number contains \(7\) so you must have changed value of contains earlier
\(1\) \(9\) \(5\) does not contains \(7\) from beginning to end so the value of contains will be \(0\) always.
Trace this program from beginning, just for binary numbers that have digits \(0,1\) or just make your own digit system with digits \(0,1,2,3\) so it will be easier to understand the code.
But this code still has a problem, it counts numbers are \(070\) or \(077\) which are actually \(2\) digit numbers. So how to fix that ?
You can add a if condition that if the position is \(1\) then you can place digits only in the range \(1\) to \(9\). Below is the fixed code.
Suppose you have been given a number \(1608\) and you want to enumerate all the numbers which are lesser than or equal to it. This can be done easily using the following process.
Let us assume we have four blanks \( ___ ___ ___ ___\) . Now what can be the first digit from left it can be either \(1\) or \(0\). i.e.
\(0 ___ ___ ___\) and \(1 ___ ___ ___\) . Now if we have placed \(0\) in the beginning it is a clear observation that we have not made any \(4\) digit number so the second digit can take values \(0\) to \(9\), but if we have placed \(1\) there then the next digit will be always \(0\) to \(6\) or else number will be greater than the required number.
In digit DP whenever we form all numbers smaller than or equal to any number we start formation with the most significant bit. Then Suppose total digits in the number is to be atmost \(4\) (like here) then we try to place each digit \(0-9\) in all the \(4\) places but keeping in mind that the number formed is always lesser than or equal to the limiting number.
I prefer recursion to be the best way to solve it and we can easily memoize it.
In recursion we always record with us the following things --
- If number formation is started or not (This can be a boolean variable). Number formation start means that we have atleast one non zero digit in the number formed till now.
- If number formed till now is less than or equal (greater is not required) to the number using the \(k\) digits from the left. Again this can be a boolean variable. To be more clear here if we have formed a number \(160 ___\) with only one place left then if we are placing any value on the \(4^{th}\) blank then we should know that \(160\) is equal to the number that can be formed by three digits from left. This decreases the total possible values. Here you can only place values \(0\) to \(7\).
- Third information is how many digit number you have formed or it can be like which position are you going to think of now.
Read the above points carefully to understand the recursion properly.
To understand we can take solve some problems in difficulty order.
Problem - 1 : Count \(3\) digit numbers containing digit \(7\)
Solution - : You can start enumerating numbers. For explanation I will use the code below.
For the first digit from right you have \(9\) choices \(1\) to \(9\). For second \(10\) choices and for third \(10\) choices. Suppose you are making a choice of second digit then if the first digit from whose recursion you jumped into this one is already \(7\) then value of contains will be true or else if you have not placed \(7\) till now then contains will be false and will become true when you will call function count by placing digit as \(7\).
When recursive programs are called then there has to be some condition where we have to stop them. So here you need to recurse until you reach a length greater than maximum length (which is \(3\) ).
Its clear that this recursion with itself stores information as position and contains.Now suppose you reach the end condition with contains as true, its like :
\(1\) \(7\) \(9\) contains digit \(7\) so return \(1\) because this number contains \(7\) so you must have changed value of contains earlier
\(1\) \(9\) \(5\) does not contains \(7\) from beginning to end so the value of contains will be \(0\) always.
Trace this program from beginning, just for binary numbers that have digits \(0,1\) or just make your own digit system with digits \(0,1,2,3\) so it will be easier to understand the code.
But this code still has a problem, it counts numbers are \(070\) or \(077\) which are actually \(2\) digit numbers. So how to fix that ?
You can add a if condition that if the position is \(1\) then you can place digits only in the range \(1\) to \(9\). Below is the fixed code.
Comments
Post a Comment