algorithm to find a number in which product of number of 4 & 7 is maximum in given range
algorithm
Solution
If I understood the problem correctly, the following should work:
- Assume all numbers have the same number of digits (if e.g. L has less digits than U, we can just fill in the beginning with 0 s).
- Let Z = U - L.
- Now we go from the first (/highest/leftmost) digit to the last one. If we are looking at the i th digit, let L(i), U(i), Z(i) and X(i) be the corresponding digit.
- for all leading Z(i) which are 0, we set X(i) = L(i) (we don't have a choice).
- For the first not 0 Z(i) check: is there a 4 or a 7 in the interval [L(i), U(i)-1]? If yes let X(i) be that 4 or 7 otherwise let X(i) = U(i)-1.
- Now fill up the rest of X with 4s and 7s such that you choose a 4 if you have assigned more 7s so far and vice versa.
Maybe an example can help in understanding this:
Given U = 5000 and L = 4900.
Now Z = 0100.
From the algorithm we set
- X(1) = L(1) = 4 (we have no choice)
- X(2) = U(2)-1 = 9 (the first non 0 digit in Z)
- X(3) = 7 (we already had a 4)
- X(4) = 4 (can be chosen arbitrarily)
Leading to X = 4974 with an objective of 2*1=2
Problem
I am stuck in a question in which lower bound `L` and Upper bound `U` is given. Now suppose in the decimal representation of integer `X` digit 4 appears `A` times and digit 7 appears `B` times. Problem is to find `X` which has maximum value of `A*B` for `L<=X<=U`. Is there any efficient algorithm to solve it?