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
Apptica
Learning and Sharing :)