Count the Number of Powerful Integers | Leetcode 2999

Summary

In this video, Techdose tackles the problem of counting powerful integers, posed in LeetCode problem 2999. The key challenge is determining the number of integers that have a specific suffix S within a given range (start to finish) while adhering to a limit on their digits. The solution requires an understanding of recursion, digit dynamic programming, and combinatorial mathematics to efficiently calculate the number of valid integers without resorting to brute force enumeration.

Highlights

• The problem involves finding integers with a specific suffix within a range while adhering to digit limits 🔍
• Recursion and digit dynamic programming are key techniques used to solve this efficiently 🌀
• Boundary cases, such as when start or finish are less than the suffix, require special handling 🚨
• The video breaks down complex logic into understandable steps, explaining dynamic programming applications 📊
• A mathematical approach using combinatorics is also discussed as an alternative method 📐

Key Takeaways

• Understand the constraints of the problem to avoid unnecessary calculations 🎯
• Utilize recursion and dynamic programming to handle digit constraints effectively 🧠
• Be aware of boundary cases, such as suffix lengths and digit limits, to avoid errors 🚧
• Learn how to adjust results based on specific conditions in the problem statement 🛠
• The approach can be extended to other problems with similar constraints and requirements 🔄

Overview

Techdose's video provides a detailed walkthrough on solving the 'Count the Number of Powerful Integers' problem from LeetCode 2999. It begins with a precise problem statement, explaining the conditions under which an integer is considered 'powerful.'

The video continues with examples that help to visualize the problem's constraints and the reasoning behind using dynamic programming and recursion. These examples illustrate how to work with boundaries, ensuring suffix and digit compliance.

Finally, Techdose delves into the code, explaining how to implement the logic efficiently. The video emphasizes understanding mathematical and algorithmic techniques to optimize solutions without exhausting computational resources.

Chapters

• 00:00 - 01:00: Introduction & Problem Statement This chapter introduces the problem of counting the number of powerful integers, which relates to a specific task from a coding platform. The problem statement gives three integers—start, finish, and limit—and a zero-indexed string S that represents a positive integer. A positive integer X is defined as 'powerful' if it ends with the string S (i.e., S is a suffix of X). Additionally, all digits in X are considered for a particular condition specified in the problem.
• 01:00 - 03:00: Problem Explanation with Example This chapter explains the concept of suffixes in strings and their application in identifying powerful integers within a specific range. A suffix is defined as a substring that starts from a given index and extends to the end of the string. An example illustrates how to identify suffixes: '25' is a suffix of '5125', but '512' is not. This sets the stage for further discussion on the significance of suffixes in string analysis.
• 03:00 - 06:00: Constraints & Expectation In this chapter titled 'Constraints & Expectation', the focus is on understanding the limitations and expectations when dealing with numeric constraints in a sequence or a number. The example given revolves around a problem where you start at 1 and aim to reach a finish point of 6,000. Key constraints include the fact that each digit used must be between 0 and 4, and no digit can exceed a limit of four. However, the start and finish points are exempt from this restriction and can contain any digit between 0 and 9. The task involves finding a solution while respecting these constraints on digits.
• 06:00 - 09:00: Generating Numbers Using Index Position The chapter discusses the concept of generating numbers based on a specific suffix, in this case, '124'. It explains that when creating numbers that end with this suffix, leading zeros are insignificant, meaning '0124' is considered the same as '124'. The chapter also explores the idea of creating variations by altering the values preceding the suffix, demonstrating with examples such as '124', '1124', and '2124', ultimately explaining that five such numbers can be generated.
• 09:00 - 12:00: Recursion Tree for Generating Numbers In this chapter, the author discusses using a recursion tree to generate numbers with specific properties. A specific example is given where the task is to find all numbers that have the suffix '10' within the range of 15 to 215, with the constraint that none of their digits should exceed 6. The strategy involves generating numbers from 1 to 215 with the desired suffix and filtering them based on the constraints. The chapter likely continues with more detailed explanation and examples of using recursion trees for similar problems.
• 12:00 - 17:00: Handling Special Boundary Cases The chapter titled 'Handling Special Boundary Cases' discusses a programming challenge of counting numbers with a specific suffix. The transcript explains a method for calculating the count of numbers from a specified range (1 to any given positive number) that end with a particular digit, by finding differences in counts across ranges. It suggests writing a single API function to determine the count of all numbers from 1 to any given number that have a particular suffix, simplifying the problem-solving process.
• 17:00 - 23:00: Digit Dynamic Programming Approach The chapter titled 'Digit Dynamic Programming Approach' delves into handling large numerical constraints using dynamic programming. It proposes dividing a problem into two parts to calculate interim results, denoted as x and y, and then returns the difference of these values to reach a solution. The chapter emphasizes understanding constraints, particularly when working with very large numbers, and uses the example of handling numbers as large as 10^15, which can be represented as a 16-digit number. The methodology discussed involves enumerating numbers between a 'start' and 'finish' value, highlighting the potentially enormous range when dealing with maximum limits.
• 23:00 - 29:00: Solution Code Overview The chapter discusses the computational limits of certain algorithms when evaluating large numbers or datasets. The narrator mentions that an operation count of about 10^15 is far too high, as it exceeds the desired limit of 10^8 operations. They consider that even taking the square root of 10^15 would still result in an unmanageable amount of operations, nearing 10^7.5 or 10^8. The focus is on finding a more efficient computational solution within the constraints of 10^8 operations.

Count the Number of Powerful Integers | Leetcode 2999 Transcription

• 00:00 - 00:30 [Music] hello guys welcome back to Techdos and in this video we will look at count the number of powerful integers which is from lead code number 2le 9 let's now read the problem statement in this problem you are given three integers start finish and limit you are also given a zero indexed string S representing a positive integer a positive integer X is called powerful if it ends with S in other words s is a suffix of x and each digit in x is at
• 00:30 - 01:00 most limit return the total number of powerful integers in the range of start to finish a string x is a suffix of a string y if and only if x is a substring of y that starts from some index including zero in y and extends to the index y.length minus one for example 25 is a suffix of 5125 whereas 512 is not a suffix right now let's look at an
• 01:00 - 01:30 example in this case we are given the start point as 1 and the finish point as 6,000 our limit of digit that we can take is from 0 to 4 not exceeding four okay and s will always be following the uh limit for every digit that means any digit in S cannot be greater than the limit whereas the start and finish will not be following the limit okay they can have any digit from 0 to 9 now in this case we are asked about uh finding out
• 01:30 - 02:00 how many numbers exist between start and finish including both the numbers in such a way that 124 is a suffix now if I can tell you such number then you can say that 0124 is such number right so you have to ignore this zero because it is insignificant so 124 will be such number or I can say that I can place a one here and I will say 1 2 4 is is one number 2 1 2 4 is such number right so likewise if you generate the numbers then you will get a count equals to five
• 02:00 - 02:30 okay so that is why five is the answer here now if you look at another example then in this case I want to find all the numbers having suffix equals to 10 uh given from start to the finish point from 15 to 215 and each of the limiting digit should not exceed six so in this case what I can do is I can find all the numbers having 10 as a suffix from 1 to 215 and then all the numbers uh which
• 02:30 - 03:00 has 10 as a suffix from 1 to 14 and if you get an x count here and a y count here then since I want to find from 15 to 215 I can just do x minus y and return the result isn't it so writing a single API of how to find uh the count of all the numbers from 1 to any given number any given positive number having the given suffix if I can write such function then I can easily solve it in
• 03:00 - 03:30 two parts and get the result x and y and just return the subtraction of the value right so this will be the idea which we will be following but before looking at any solution let's look at the constraint in this case the start and finish value is maximum 10 ^ of 15 which is approximately a 16digit number right so if you are trying to get enumeration of all the numbers from start to finish where in the worst case start will be 1 and finish will be 10 ^ of 15 it will
• 03:30 - 04:00 definitely take 10 ^ 15 operations minimum right and on top of that you have to analyze all the digits as well but I'm not counting that this is way greater than your 10 ^ of 8 right since I want to run this algorithm within 10 ^ 8 so I cannot do such kind of thing even if I would do in root of uh square root of 10 ^ of 15 then that will be approximated to be 10 ^ of 7.5 or you can say 8 so I have to do something even
• 04:00 - 04:30 better than square root of n right and you can assume that I have to solve this problem in log order simply log of n order where n is actually the finish right so this should be my time complexity expectation out of this problem now once you know what to expect of this algorithm uh then it will be easier to think the solution in such lines isn't it uh so the limit value is from 1 to 9 okay and the slength which
• 04:30 - 05:00 is the suffix length will always be having the maximum number of digits less than equals to the finish number right so there will never be a case where the suffix asked is having more length than what the finish value is given but this does not mean that the finish value cannot be smaller than S you should always take note of this because the finish value can be 1 2 3 4 and the S value can be 5,000 and I will be asking you to find from start start can be anything which is less than equals to
• 05:00 - 05:30 finish right so I can ask you about find the count of numbers which has 5,000 as a suffix given from start let's say start is 1 1 2 1 2 3 4 so the count will always be zero because the finish value is actually less than the s value right so I'll show you all these boundary cases but from this don't assume that it is saying uh that s is less than equals to finish no it is just saying that the number of digits is less than equals to the number of digits in finish but that does not imply that s is less than
• 05:30 - 06:00 equals to finish fine s is only containing numeric digits which are at most limit and S does not have leading zeros fine once we have understood everything uh let's now look at some observations so according to what we have studied start uh is less than equals to finish i can say because that was already mentioned in the constraint right start is less than equals to finish but S may not be less than finish as I explained earlier and start also can be either less than
• 06:00 - 06:30 equals to or greater than s the second point is any digit asset I should be always less than equals to limit this rule is only followed by the numbers that we will be generating and s but this is not necessarily true for start and finish fine so the start can be like let's say 142 finish is 2 4 6 38 while the limit was only four and the s value will always have all the digits within the limit and whatever number we will be generating from start to finish having suffix s should also have all the digits
• 06:30 - 07:00 less than equals to limit that we should take care of now the maximum number will be no more than 16 digits as it is mentioned maximum number is 10 ^ of 15 now once you have understood some constraints let's look at an idea in this case if you are given start and finish value with the limit value being seven and s value being 10 our goal is to find all the numbers from start to finish with s as the suffix that you know so we need to enumerate all the
• 07:00 - 07:30 values greater than equals to start and less than equals to finish so that enumeration can be 1 0 2 1 0 2 1 1 0 4 1 0 and so on so as I already told you that you can actually count uh all the numbers from start to finish by counting all the numbers from one to finish and subtract from one to start minus one so this is your x value this is your y value as I said and x - y will give you the count of all the integers in the range of start to finish inclusive of
• 07:30 - 08:00 both the values which will have s as the suffix so in this case if you take count of 15 to 21 34 then you can take count from 1 to 21 34 minus 1 to 14 and you will get 18 minus 1 which is 17 this is a simple idea right now I'll keep telling you about the boundary cases there are multiple boundary cases for this problem in this case if the start value happens to be less than s okay start value happens to be less than s like let's say the start is 8 and the s
• 08:00 - 08:30 value that means the suffix should be 10 then does it even matter that I will be counting uh the numbers from 1 to start minus one where the suffix will be s well the suffix will never be s this count will always come out to be zero when the start value is less than s right because you have to have a number at least greater than equals to s to have s as a suffix you cannot have a smaller number than s and say that I
• 08:30 - 09:00 will have s as the suffix that is not going to happen so this is one boundary case where I will say that if start is less than s then counting from one to start minus one will always be zero so I will not calculate it rather I will just return the answer from start to finish as one to finish simply and and you just return the value x as the answer right but if finish is less than s then you can imagine that the count will always be zero because s can never be a suffix i showed you that example while uh
• 09:00 - 09:30 reading the question right that finish can also be less than s even though the number of digits can be same in the worst case right so in that case I will not calculate anything I will simply return zero so I think this idea is clear now let's see like how to generate the numbers digit wise what we should take care of while we are generating the numbers limit is important because I cannot choose any digit which is exceeding the limit but limit is not the only thing that I should take care actually I will be looking at the start
• 09:30 - 10:00 digits and I should not exceed the limit yes but I should also not exceed the corresponding digit otherwise I will be exceeding the uh amount that I should actually look at right so let's say that this is not start but this is finish let me just assume that it is finish and I want to calculate all the all the numbers from one to finish all the numbers from 1 to finish where the suffix is always equals to 21 as given
• 10:00 - 10:30 in this case suffix is always equals to 21 so how to generate such numbers now for for creating the numbers I will assume that it is a five-digit number from 0 to 4 so for the first digit here the options will be always minimum of 2a 3 minimum of whatever you are looking at sat i comma the limit that is a sensible choice to make because because if I'm
• 10:30 - 11:00 generating all the numbers from one to finish then I cannot generate anything which is greater than finish while if I had taken an option three here thinking that limit is allowing me to have a three then as soon as you place three at the most significant digit then this number will definitely whatever you put here it does not even matter it will exceed the value finish that I do not want to do right so that is why since I do not want to exceed finish I will be taking the digit option as minimum of
• 11:00 - 11:30 the current digit comma the limit if this digit was let's say seven then still I cannot take from 0 to 7 because the limit is not allowing us to take seven or maybe even anything after three that is not how the problem has been framed okay so I'll always take minimum of limit comma the current digit and that is two so how many options do I have here I have 012 as an option three options are present right now if I if I move forward to one for whatever you had
• 11:30 - 12:00 chosen here what can be the options for this one now if you if you carefully think about it if you had not chosen these two let's say then you had chosen 0 and one then I can select any number from zero to limit simply I can choose here zero i can choose one i can choose two i can choose three but definitely I cannot take any digit greater than the limit and e even though this value was one because if you had already taken a
• 12:00 - 12:30 smaller digit for a significant digit like I if I had taken a zero or one as the on on the significant side that that is to the left of this digit which I'm trying to fill then I can safely exceed the SI value okay this is your SI value so I don't need to be barred from SA if I had taken a smaller number on the left side than the actual asset I then I have the luxury of choosing the number from one uh I mean from zero to limit and that is what I'm doing but if you had chosen two here on the left hand side
• 12:30 - 13:00 that is actually matching up with the SI then the next number should be taken as minimum of 1a 3 these are the two cases that you will see okay so if you had ch uh chosen any one of this zero or one I will be ending up with four options from 0 to three that is from 0 to limit but if you had chosen two then you will only have two options which is 0 and 1 which is the minimum of this 1a 3 right so I
• 13:00 - 13:30 have already enumerated this case that I I will be managing this with a boolean variable is tight so this tight variable will tell me if I had actually used a digit which is which is uh equals to set I every time on the left hand side every time on the left hand side so if is tight is false this means I have the luxury to choose the current digit from zero to limit whereas if the isite is true that means I have already chosen a
• 13:30 - 14:00 two on the left hand side so I have to choose minimum of limit start position and this second case should always hold true for the first digit whenever you start you should always start with the tight limit okay so that tight limit will always be true for the zero digit and depending on what you have filled here it will be propagated to the next digits now let's say that you have taken a two here so the tight value was already true and you have taken a two so for the digit number one the tight value
• 14:00 - 14:30 will be true as well right now I have only two options 0 and one now let's say you have taken a zero here you have taken a zero here so the tight value will become false for the second digit and after that you can choose all possibilities but not uh going to five this five is of no use for us i will take only from 0 to limit if the value is false from 0 to limit right because I cannot exceed the limit so I will try to utilize 0 1 2 3 4 I mean 0 1 2 3 in such
• 14:30 - 15:00 case right but if I had chosen one then the tight limit will not be false but it will be true and so I will be taking the options minimum of 3a 5 which will still come out to be same in this case right but let's say that the tight value was true here and then it became false here because you had chosen a zero so after this once the tight value becomes false the tight value will always remain to be false whatever option you take it does
• 15:00 - 15:30 not even matter because once let's say you had taken the 08 digit to be two and the first digit to be zero after this it does not even matter what digit you are putting as long as these digits are uh within the limit because this number starting with 2 0 will always be less than the number starting with 21 okay so as soon as you break the tightness constraint and make it false it has started with true but if you make it
• 15:30 - 16:00 false then after that you have to always uh take the options ranging from zero to limit okay if you did not understand this please pause it and rewind the video and and again watch it back right so using this idea you don't even have to go with recursion dynamic programming and all these solutions i'll show you why it is a DP solution and recussion but what you can do is you can simply use maths because you can just take care of the boundary cases which I will be telling some of them I told you some of
• 16:00 - 16:30 them I'll be telling you take care of that and you keep multiplying the possible options that you can put but I will not be going with the math solution because this may not be very easy to understand for most of you guys and uh I think it will be too much of an overkill so I will be just doing the standard algorithmic solution for this problem now there are three questions to discuss in this scenario what is the range of the digits at each index that I have
• 16:30 - 17:00 already explained you how to how to take care of that using the isite and how to track what should be the range so the tracking should be done with the is tight variable which is a boolean type and how to guarantee that the suffix s is generated now this one I didn't tell you let me tell you now that how to guarantee that you generate you end up with the suffix s whatever is the s value because I cannot just keep on generating all possible numbers because that will just be like a for loop right if I had run a for loop from start to end then that would be same as whatever
• 17:00 - 17:30 method I'm telling you right now there is no difference to it and this is a recursive method and the iterative method is already taking a lot of time so what I will do is I will find the size of this s the size of this s is two that means two digits s are present right so as soon as I reach to that index as soon as my current index current index is reaching to the second last digit right second last digit because the size of S is two if if the
• 17:30 - 18:00 size of S was three then I would say the third last digit i will show you in the code how to how to check that out but I think you can do that easily so if you reach to the second last digit then you do not apply your options okay then we will not be taking a minimum of limit comma start or zero to limit no none of these options are going to run i will be simply forcing this second last digit to be two and the last digit to be one there is no option for this digit three
• 18:00 - 18:30 and four it has to be two and one okay it is it is it is only having one option because I will always be generating a valid number and a valid number is one where all the digits are within the limit and the second condition is the suffix should always match with s now how do I know that uh whatever if I'm forcing this two and one then uh it will be following that all these digits will be always less than equals to limit well it was already mentioned in the question that each of the digit asset I will
• 18:30 - 19:00 always be uh within the within the limit range you see s only contains a numeric digits which are at most limit so if I am forcing them to be two and one because I want to match the suffix then they are already following the limit okay I don't have to check for it so that is how I will be guaranteeing the suffix X is generated okay so the suffix will only have one option so the options will only rotate for the prefix which do
• 19:00 - 19:30 not include the suffix right they will only create so many uh possibilities that you need to count so I think you got an idea of how to generate the numbers digit wise now once you have got that idea let me show you a recursion tree diagram of how to use recursion to generate the numbers so I will be taking a limit value two and let's say the s value being 21 i have taken a start value to be 1 1432 so maybe I want to generate all the numbers from 1 to 1 432
• 19:30 - 20:00 or you can say that this is my finish number anything is fine right so I have a four-digit number now you think about this position 0 1 2 3 this is position 0 1 2 3 how many suffix uh items do we have we have two digits so this will go to the suffix side okay now once you are not at the suffix side then how many options do you have right in the beginning you check it out at this zero position uh since the tight value will be true because you will
• 20:00 - 20:30 always be starting with the is tight value true the option will be minimum of this digit 1 comma limit so that will be only a one so you can use 0 comma 1 here so you have two options either you use zero or you use one that's it so that is why at position number zero this is not a number this is just a position right so at position number zero you have two options 0 and one well if you take the zero option then you know that the isite value will become false because you have
• 20:30 - 21:00 started with a digit which is smaller than the uh that than the digit which is present in the finish number or the start number right so as soon as you put a zero here the tight value will always be false for all the subsequent nodes no matter what you put okay because you have already put a zero so the number is going to be smaller than whatever is the given number so you are not going to exceed that anyway so the tight value becomes false as soon as you pick a zero now at position one the option will only
• 21:00 - 21:30 depend on limit it will not depend on sat i because the tight value is false so I'll be going from 0 to two that means I can pick 0 1 or two at this position 0 1 or two having picked this zero okay now if I have done that then I will be going to index two now at this point nothing matters tightness and nothing nothing matters at all at this point I will be forcing the value to be set as 2a 1 at index two and at index
• 21:30 - 22:00 three so at index two and three I will have only one option coming out you see I will exactly have one option coming out and therefore this will give me one possibility right what is that number 0 0 2 1 0 0 1 is one number right which is in the range of 1 to finish you can say right so this is a valid number and this will be contributing plus one to our count and then we will be backtracking we will be backtracking so when we backtrack we will be backtracking from
• 22:00 - 22:30 the suffix items altogether and go back to index one because there is no other branching for any of the suffix indices it just had one option so from one you can try to put uh the other option that is one right so if you put that then the then the rest of the two options will definitely be your own 2a 1 that is fixed so this will also contribute plus one to our option right this will also contribute + one and then you have tried all possibilities from one you go back to zero now at zero if you had put a one
• 22:30 - 23:00 then for the next time you will have to take the minimum of 4a 2 which again happens to be two itself right so you will have 0 1 2 as three other options and so this will contribute + 1 + 1 + 1 to the count and and therefore the total count of numbers where 21 is the suffix and you count from 1 to 1432 will come out to be six only okay okay so I think
• 23:00 - 23:30 this is clear how to generate all the numbers using recursion and using the isite uh as your uh boolean type to say what will be the uh range of digits that you can use will it be from zero to limit or will it be from 0 to minimum of limit comma set I fine so once you have understood this then let's look at the special boundary case in this case if you have the finish value is let's say 2632 and the limit value to be 8 where s is equals to
• 23:30 - 24:00 35 then you will end up with a number where you choose a two where the value was true then you go and put six where the stat value was true and then you are forcing to put three and five at the end because we are not checking anything at the end that I'll be showing you in the code so if you happen to force a number like this 2635 then this will get counted but this is actually outside of your range from 1 to 2 632 and so this is invalid this is a case where an extra
• 24:00 - 24:30 counting can happen because we are forcing the numbers at the end okay so this happens only when the tightness on the left hand side leaving the suffix items for all the digits on the left hand side the tightness always happen due to SATi that means all the digits in the finish or all the digits in the start whatever we are calculating with right the tightness never happened due to limit but it happened due to the
• 24:30 - 25:00 digits present in the finish or the start so if if that is the condition which happens then you will end up with a number which will be greater than the finish value which does not fall in the range and so it has to be subtracted by minus one value simply okay but this condition will never arise if the suffix of the finish is greater than equals to s because if this was let's say 38 instead of being 32 then do you think that 2635 will be outside of range it is not going to happen okay so this
• 25:00 - 25:30 condition uh arises only when two things uh happen together that is the suffix of your given number finish or start whatever the suffix of your given number is less than s that is the first condition and the second condition is all the numbers on the left hand side all the digits on the left hand side are actually less than equals to limit if that is the case that happens then this overounting uh scenario will happen and
• 25:30 - 26:00 it will happen only once okay so this has to be taken care of by subtracting a minus1 value so this uh check has to happen so I'm just reading out my statement this will work only when the suffix of finish is greater than equals to s provided limit do not cause tightness that is limit is greater than s i this will work if the limit is equals to five even uh because the tightness using limit was applied on at least one digit because if your limit value was five then you could not place
• 26:00 - 26:30 a six here you have to place a five and so this 35 2 535 will always be within the range of finish you have to think over it a little more carefully right therefore we need to adjust this case by subtracting one you have to check this case separately right so I think I think it is clear uh now once it is clear let's look at the optimal recussion memorization using dynamic programming approach right I will be showing you why this is dynamic programming as well in
• 26:30 - 27:00 this case I have taken just a simple example from 1 to 2 33 32 and I will be trying to calculate how many numbers are generated from 1 to 2 32 uh having the suffix 33 with a limit value four once you learn about how to calculate from 1 to 2 32 then you and just repeat that process from one to start minus one but start equals to 1 is a special case where one uh I mean from 1 to zero it does not make sense right
• 27:00 - 27:30 so when start equals to 1 then you just calculate from one to finish and that's all that's the count fine now in this case I need to generate four-digit numbers right so I will be taking options of four digit 1 2 3 4 now if you look at it this is 0 1 2 3 as the positions uh now I have the first digit with the tightness value true that is where I will be starting with tightness value true okay these are all the positions that I have marked in the node since the tightness value is true I have
• 27:30 - 28:00 to consider the minimum of 2 4 which will be two so I will have three options here either to place zero or one or two and that is why there is three branching 0 1 2 now if you pick any of these zero or one the tightness value is going to be false and as soon as tightness is false the entire subree the entire subree will never have tightness value true again it will always be false because a significant digit became lower than your finish number then that means
• 28:00 - 28:30 it is never going to exceed that number okay so this entire two sub trees will always have tightness value false and hence I will not be writing it again so let's say that you place a zero here so what will be the option at this position number one it will only depend on the limit it will not depend on this three okay because the tightness is false so I will be putting 0 1 2 3 4 as five option options okay so so at one I have five options and hence we have five branching now for the last two options that is 2 3
• 28:30 - 29:00 since it is the suffix part right i will be forcing the numbers 3 three which is in s I have to force it so at 2 and 3 there will be exactly one option and that is why there is exactly one branching so all the possibilities will occur only due to index 0 and one index 2 and three do not contribute to the count of possibilities fine so if you follow this one branch then this will contribute plus one to the count okay plus one to the count i'm just showing you the recussion approach right now then here
• 29:00 - 29:30 you will have plus one to the count plus one to the count what is this second number this number is zero you have you had put a zero here right and this is zero then this will be 3 three you see this I have already written 33 so this number that you get is 0 0 33 this is within the range and it is fine within the range of one to finish right then this number is 0133 so 0133 is also valid this number is 0233 so you see how the numbers are
• 29:30 - 30:00 getting generated this number will be 0 33 33 this is also + one then you have 0 uh 0 4 33 3 0 4 33 3 and this is also valid right so you keep adding + 1 + 1 like that so how many uh count did you have right now 1 2 3 4 5 so I have plus five count by branching from one okay now if you go back to this zero after branching and you again make a call to this one then this means that at zero
• 30:00 - 30:30 position since you had put a zero now you are trying to put a one so the tightness value will still be passed as false because at zero position uh you have two as the digit value and anything below two will be making the tightness as false so if you have tightness at false then in how many ways you can fill these three digits in such a way that 33 is the suffix will be the same as how many you had uh you had generated placing zero on the left because
• 30:30 - 31:00 whatever you put in the left has no significance provided the tightness value is the same that means other than two if you place zero or one it does not matter for zero whatever was the count of combinations for one also it will be the same count of combinations and that is how uh you could also solve this problem with maths simply by combinatorics multiplying the number of possible combinations right so that is why I will say that this is a repeating sub problem because the sub problem in
• 31:00 - 31:30 this case is defined only by the position as well as the eastite value East type value either it is true or false because if it is true then I will be taking the digit as minimum of limit comma sat i otherwise if it is false then I will be taking from zero to limit so this is affecting our number of combinations and position is affecting because given the position it will define how many digits I have right so position comma is tight will only define
• 31:30 - 32:00 our sub problem so if you see here the position for all these three are one but here the tightness value is false and here also false but here it will be true because if you put a two which is the limit I mean it is equals to si then the tightness value will be true so this one and this one are the same repeating sub problem but this one is not repeating okay this is a different sub problem so similarly I will be just returning a value five because I will be saving it somewhere right so I can simply make a table a DP table of size position and
• 32:00 - 32:30 you know that this is a 16digit number so I can simply take 17 size which is from 0 to 16 and uh the tightness value can no more be true and false so I'll be taking DP of uh 17 by 2 and preassign it with all the minus1 values because I know that all the numbers are positive here and the counting can never be negative so if I put a negative number uh then I can say that if I want to get uh the solution for the sub problem let's say
• 32:30 - 33:00 position number one and the tightness value being false which is zero and if it says that it is already minus1 this means this is not calculated and you need to calculate it the first time you calculate it we will be filling up this value with the count which is five and the next time when I see the same sub problem I will be simply returning five so the value that you get at 0 is 5 + 5 which is 10 now for two this value is true right this value the tightness
• 33:00 - 33:30 value is true so this is a different sub problem this sub problem is 1 comma 1 and this value is still minus one in in the dp table or you can say the memorization table okay now since this is not yet solved I will be solving it and so at the first index when the tightness value was true that means you had put a two on the left hand side what all options I have at index one index one has uh value three right it has index three so I mean the the digit
• 33:30 - 34:00 value is three so I can put 0 1 2 3 which is minimum of 3 4 so initially I had five options 0 to 4 now I have four options 0 to 3 so you see the branching is only four here the branchings were five so you have four branching and as soon as you pick any of these values 0 1 2 3 I mean let's say you put 012 you are going to the suffix index and that suffix index you don't have any option but you have to just um force yourself
• 34:00 - 34:30 to put 3a 3 right so this will be giving you plus one count plus one count plus one count plus one count even the tightness value wouldn't matter when you go to the suffix index because at this point you just have to force yourself to put the value and I already proved that this will be always within the limit because all the asset I is less than equals to limit so that is why you can just force yourself to put 3A 3 so now you have got a four count here so you can override this to four and you will be returning the value okay so this
• 34:30 - 35:00 value is coming out to be 14 but in reality here the value should not be 14 the actual value should be 13 only because I showed you the boundary case about overounting so here what is happening what is this last number if you see 2 3 33 3 this is 2 3 33 3 as the last number but if you see the finish value it is 2 33 32 so I'm exceeding this value right so this should not have been counted actually so after doing all
• 35:00 - 35:30 the counting whatever count you got maybe this is correct or maybe you need to get one less value which will be correct any of these two values will be correct so you have to check for correctness i told you about two criteria you have to check the suffix value the suffix value 32 if it is greater than equals to s then you don't need to do anything it is fine but you see that the suffix value 32 is less than 33 which is the s value so that means there is a chance that we might
• 35:30 - 36:00 have to adjust uh adjust a minus one value because there there might be a chance of generating a number outside of the finish range and and that I have to check with all the prefix items leaving out the suffix value all the prefix items I have to check all the digits if all of these digits are always less than equals to limit then there is a chance that uh you will be able to generate a number which is outside of the range of
• 36:00 - 36:30 finish and yes it is true in this case 2 3 is always less than equals to 4 so that means I I have ended up with one extra count so I will be adjusting it with minus1 and so my actual answer will be 13 and that is how the answer will be 13 here right so I think this idea is clear this is also called your digit dynamic programming because this is dynamic programming applied on digits fine if you are good with recussion then this will be easy for you to understand even
• 36:30 - 37:00 now having understood this how many sub problems will be there you know that in the problem statement it was mentioning about 16 digits and uh 16 digits with uh simply two tightness constraint true and false so I have taken 17 by2 so it will be 34 so maximum unique sub problems will only be 34 but even though problems are unique or or not unique the maximum branching that a node can have is 10 which is from 0 to 9 if the limit value
• 37:00 - 37:30 happens to be nine right so considering all those cases your number of sub problems will be maximum digits into two which is the digit is counted by log base 10 of the largest number and let's say that largest number is finished number let's assume that it can also be s right but that boundary case I will already be handling if I even need to solve it so I will always take finish as the largest number so log of finish uh base 10 would be like the number of sub
• 37:30 - 38:00 problems in this case uh I mean multiplied by two definitely due to the tightness and and the total recursionary node will be total number of sub problem and the options per node so you can have 10 digits or 10 options per node uh all these are constant so you can assume like log of finish will be the time complexity and the space complexity will also be same because even though it looks like a two-dimensional table it is just a very uh simple size table which is log of finish right 2 * log of finish
• 38:00 - 38:30 so I think we have understood the entire solution let me know in the comment section if you have followed the digit dynamic programming or the maths combinatorics method to solve this problem let's now look at the code if you are someone who is looking to prepare for top product based company within a limited time of just 3 months then we have brought for you both the DSA and the system design live interview training program the most important feature of this program is you get a filtered and condensed structured
• 38:30 - 39:00 curriculum in-depth discussion of all the topics and my guarantee of your understanding one-on-one guidance with me and live weekend classes to know more about the training you can WhatsApp us on this given number in this problem we are given the start finish limit and suffix so I will be using the stoall function which is string to long integer in C++ okay you can check out in your language how to do that i have already provided Java and Python code so I'll be using stole everywhere because it is
• 39:00 - 39:30 easier to compare two integer numbers or long long numbers rather than comparing two string so uh string to long on the suffix will give me the suffix value and I will convert finish to string called finish str and uh start minus one to string which is called start str now find the number of digits you can use this formulation or you can take the log base 10 of the finish number and plus one this will give you the number of digit which is the same as finish
• 39:30 - 40:00 digit and start digit so these are the two ways you can follow anything so this seems to be a less complex method so I have followed converting to string now I will be calculating the count of all the valid numbers from one to finish in up to finish and one to start minus one in up to start but I will only calculate up to finish if the finish is actually greater than equals to suffix value otherwise we will always have zero as the answer right and the same goes for start i will always calculate from
• 40:00 - 40:30 one to start minus one if the suffix value is less than start otherwise if you do not have any any count you already know it will be zero then why don't you just replace with zero why are we solving it right so I have written a utility function here solve up to so that I don't have to write it two times okay otherwise we would have to write this piece of code two times so in this particular case I'll be calling solve up to finish string finish digits limit suffix similarly start uh string start
• 40:30 - 41:00 digits limit suffix right so let me show you uh these two piece of code so the First utility function is your solve up to in this case I will be setting the DP table to minus one as I said the count will be minus one initially and taking the count value in result then I will be checking if an adjustment by doing minus1 is required or not required and accordingly I will be uh sending the result back now the adjustment code is written on top but before uh seeing that
• 41:00 - 41:30 let me tell you about the digit DP so this is the application of your recursion code with digit dynamic programming so in this case I'm getting the number the current index that I'm looking at the maximum digits that you have in your given number the isite value the limiting digit and uh the suffix that you want to match up with so if the index reaches to max digits that means you are out of bound then you return a value one because we have reached to the end of the recursion tree
• 41:30 - 42:00 diagram at the leaf node so we have generated one valid possibility i have already shown you in the recursion tree diagram if you reach to the end you will add plus one that means you will be returning a value one simply and if you have not reached to the leaf then if this sub problem has been solved already then you return the answer without solving it back again otherwise if it is uh the sub problem where you are reaching for the first time then you will be looking at the low and high value this low and high value
• 42:00 - 42:30 will tell you if you are trying all possible digits at a point from low to high you have to try okay so the low will always start at zero fine the suffix length is the suffix dot size simply and I will be checking if the index is actually in the range of the suffix because these all may be the indices and the last two digits may be the suffix but how will you identify if the index is greater than equals to max digits minus suffix length that means you are inside the suffix uh index that means you are at the end ind part of the
• 42:30 - 43:00 indices in that case you have to see what is the suffix index so the suffix index uh will be will be calculated simply and after that the low and high value will be set exactly equals to the suffix because then I cannot iterate if the if the suffix has to be three here then it has to be three so the low value will be set to three and high value will be set to three because if I try using a for loop putting all possible digits there then it should be only one
• 43:00 - 43:30 possibility we we do not want to try any other possibility right so that is the reason we have set this value like this otherwise if we are not at the suffix indices but we are on the left side of the suffix indices then the high range will be decided by the eastight because if eastight is true uh then that means I have to take the minimum of limit comma set I otherwise I have to take just limit as the high value after coming out I will be calculating the total
• 43:30 - 44:00 possibilities at a given node and I will be trying all possible digits that I can place at a certain index right I will try that out so I will try it out using a for loop and I will always be calculating what should be my new tight index because if my limit is from let's say 0 to 4 if I place anything from 0 to 3 the next recursion call should always have the east tight value as false okay so that is what I will be doing here using an end operation otherwise if the
• 44:00 - 44:30 eastight was true here and this four is also coming because of the tight uh value then actually I should be sending the eastight value to be true even even forward in the next digit right so that is how the new tight value will be calculated and I will be adding uh the total possibilities for each of the digit positioning and after that I will be returning it back but before returning I will be saving it into the DP table because the sub problem has now
• 44:30 - 45:00 been solved now checking back to the subtraction case I told you that if you have a certain suffix let's say it is 32 and the number that you are trying to place like let's say S was equals to 38 now if this suffix was somehow let's say it was 42 it was greater than equals to S then it is fine you do not need to adjust anything right so this first check here boolean subtract do I actually need to subtract so if the
• 45:00 - 45:30 suffix of the number here suffix of the number if it is less than the given suffix then yes then you might need to check the prefix items otherwise if this 42 is already greater than equals to 38 then you will just return zero that means you will return a false value i don't need to subtract but in this case if it is 32 then 32 is less than 38 so the boolean subtract will be set to true and if it is true then we will be checking all the prefix items now if it
• 45:30 - 46:00 so happens that you have 2 six and the limiting value was let's say uh seven or it can be six it can be anything greater than equals to six for this particular example now if any of these digit values are actually greater than the limit that means if the limit was from anything from 0 to 5 then at least one digit is greater than the limit in that case this subtraction is not uh is not done otherwise if it is from 6 to any other
• 46:00 - 46:30 number 6 to 9 then for this example we need to adjust the value you may have to enumerate and see for yourself how it is working right so this is the entire piece of code and I hope it is clear if you still have any doubt then feel free to comment below and I'll try to help you as soon as possible like and share our video and subscribe to our channel in order to watch more of this programming videos see you guys in the next video thank you