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