Apptica

In the last post i discussed few basics required for DP on digits. Now i am going to explain you a  problem so as to relate to what that post meant.  Problem : Given a range \([L,R]\) , how many numbers are there such that its two adjacent digits form a number which is a perfect square. Solution: Problem asks us to count numbers like \(125\) as \(25\) is a prefect square, \(198\) is not valid as there are no two adjacent digits for which the number is a perfect square.  First of all let us discuss some state variables.  \(pos\) : \(pos\) tells us that you are going to place any digit on this position \(isequal\) : Discussed already in previous post, this tells us whether the number formed till now is equal to the prefix of the limiting number starting from \(1\) to \(pos-1\). For example let us count numbers less than \(1269\) then for the status \(126 __\) , \(isequal\) will be \(1\). \(started\) : This tells us whether number formation is started or not. In simpl

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 re