Given an integer n (1 <= n <= 1010), count the number of valid numbers in the range [1, n] (inclusive).
Note: A number is called valid if digits 2, 4, and 8 occur in it with equal nonzero frequencies. For example, numbers 248, 284824, and 2148 are valid, whereas numbers 3456 (different frequencies) and 356 (zero frequencies) are not.
Examples:
Input: n = 300
Output: 2
Explanation: 248 and 284 are the only valid integers in range.Input: n = 1248
Output: 7
Explanation: 248, 284, 428, 482, 824, 842, 1248 are the valid integers in range.
Approach: To solve the problem follow the below idea:
Use digit DP to count the numbers in the range [0, n] where the count of digits 2, 4, and 8 are all equal and greater than zero.
Follow the steps to solve the problem:
- It iterates through the digits of the input number n from left to right, considering each digit keeping track of the counts of the digits 2, 4, and 8 using the variables two, four, and eight.
- By using memoization to store intermediate results for avoiding redundant calculations and overlapping.
- For each digit we recursively explores two possibilities either the current digit is less than the corresponding digit in n or it’s equal.
- Then now If the flag is not set (meaning the current digit can be less than the corresponding digit in n), it considers all possible digits less than the current digit and updates the counts of 2s, 4s, and 8s accordingly.
- If the flag is set (meaning the current digit must be equal to the corresponding digit in n), it considers all possible digits from 0 to 9.
- The base case checks whether all three counts (two, four, and eight) are equal, greater than zero, and not equal to 0. If this condition falls true the current number is considered valid.
- Finally returns the count of valid numbers found during this recursion.
Below is the C++ implementation of the above approach:
C++
// C++ code for the above approach:#include <cstring>#include <iostream>using namespace std;int dp[10][10][10][10][2];int solve(int ind, int two, int four, int eight, int flag, string& s){ if (ind == s.size()) { if (two == four && eight == four && two != 0 && four != 0 && eight != 0) return 1; else return 0; } if (dp[ind][two][four][eight][flag] != -1) return dp[ind][two][four][eight][flag]; int ans = 0; if (!flag) { for (int i = 0; i < s[ind] - '0'; i++) { ans += solve(ind + 1, two + (i == 2), four + (i == 4), eight + (i == 8), 1, s); } ans += solve(ind + 1, two + ((s[ind] - '0') == 2), four + ((s[ind] - '0') == 4), eight + ((s[ind] - '0') == 8), 0, s); } else { for (int i = 0; i < 10; i++) { ans += solve(ind + 1, two + (i == 2), four + (i == 4), eight + (i == 8), 1, s); } } return dp[ind][two][four][eight][flag] = ans;}// Driver codeint main(){ int n = 1248; memset(dp, -1, sizeof(dp)); string s1 = to_string(n); // Function Call cout << solve(0, 0, 0, 0, 0, s1) << endl; return 0;} |
7
Time Complexity: O(10^(log10(n))), number of recursive calls for string s of n length, which is O(log10(n)), at each level of recursion loop runs 10 times.
Auxiliary Space: O(n), as we are using 4D dp array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
