Find the number in a range having maximum product of the digits

Given a range represented by two positive integers L and R. Find the number lying in the range having the maximum product of the digits.
Examples: 

Input : L = 1, R = 10
Output : 9

Input : L = 51, R = 62
Output : 59

Approach : The key idea here is to iterate over the digits of the number R starting from the most significant digit. Going from left to right, i.e. from most significant digit to the least significant digit, replace the current digit with one less than current digit and replace all the digits after current digit in the number with 9, since the number has already become smaller than R at the current position so we can safely put any number in the following digits to maximize the product of digits. Also, check if the resulting number is greater than L to remain in the range and update the maximum product.
Below is the implementation of the above approach: 

9
59

Time Complexity: O((logr)²), where r is the given number.

Auxiliary Space: O(logr) where r is the given number.

Another Approach:  It can be solved using Digit Dp

Key Points of Observation:-

1.  As we know we use tight in digit dp to check whether the range for this digit is restricted or not,same here we will use tight ta and tight tb (basically two tight conditions) ,where ta will tell us

the lower_bound of the digit and tb will tell us the upper_bound of the digit and reason to use two tight values is that we have to calculate the maximum product,it may be the case as:-

max(l,r) ? max(r) – max(l-1) and our integer should lie in a range from l to r.

2.  Let suppose the range values as, l=5 and r=15 , so to make size equal we should append the zeroes in front of number after converting to string and taking care of leading zeroes while calculating the answer,

Dp states include:-

1) pos  

• it will tell the position of index from left in the integer

2) ta    

• it represents the lower_bound of a digit,we have to make sure number should be greater than or equal to { l }
• Let suppose we are building a number greater than equal to 0055 and we have created a sequence like 005, so at the 4th place, we can’t put digit less than 5,that will only have digits  between 5 to 9. So for checking this bound, we need ta.

Example : Consider the value of  l = 005
Index   : 0 1 2
digits  : 0 0 5
valid numbers like: 005,006,007,008...
invalid numbers like: ...001,002,003,004

3) tb    

• the upper_bound of a digit,we have to make sure number should be lesser than or equal to { r }
• Again let suppose we are building a number lesser than equal to 526 and we have created a sequence like 52, so at the 3rd place, we can’t put digit greater than 6,there we can only place between 0 to 6. So for checking this bound, we need tb

Example : Consider the value of  r = 150
Index   : 0 1 2
digits  : 1 5 0
valid numbers like: ...148,149,150
invalid numbers like: 151,152,153...

4) st      

• used to check for leading zeroes( as 005 ~ 5)

3.  Constraints: l and r (1???l ??r???10^18)

Algorithm:

• We will traverse i from start to end on the basis of tight ta and tight tb as:

start = ta == 1 ? l[ pos ] - '0' : 0;
end = tb ==1 ? r[ pos ] -'0'  : 9;

• Firstly we will check for leading zeroes as :

if ( st == 0 and i = 0) then multiply with 1,else multiply with i

• For every position we will calculate the product of sequence and check whether it is the maximum product or not and store the corresponding number

int ans = 0;
for(int i = start; i <= end; i++){
  int val = i;
  if (st==0 and i==0) val = 1;
  ans = max (ans, val * solve (pos+1, ta&(i==start),tb&(i==end) ,st|i>0);
}

C++ implementation:

l= 52
r= 62
Maximum Product: 45
Number which gave maximum product: 59

Time Complexity: O(logN), where N is the maximum number between L and R. 
Auxiliary Space: O(logN)