PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Abhishek Verma
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
Digit DP, Math
PROBLEM
Given an integer N, count the number of integers x between 0 and N inclusive such that product of digits of x is \geq K! where K is the number of digits of x
Let’s call a number x good if the product of digits of x is \geq K! where K is the number of digits of x.
QUICK EXPLANATION
- All good numbers are up to 10^{24} as 24! \geq 9^{24}
- Order of digits is irrelevant if upper-bound N is ignored.
- The number of distinct digit products possible for all numbers is 486980 (found by running a program)
- Find a way to answer the query: given d and v, find the number of d digit integers having digit product \geq v. Let’s denote this by f(d, v)
- Use Digit DP along with f can be used to count the number of good numbers up to N
EXPLANATION
Bluff in constraints
N \leq 10^{100} is a bluff, not the real constraints. Let’s see how.
For a D digit number, the maximum possible product is 9^D, and we need it to be \geq D!. After D >= 9, factorial grows faster than 9^D as D increases, so there must be a value L where 9^D \lt D! holds for all D \geq L. This way, we can see that there’s no good number with L' \geq 22 digits, or 10^{21}.
Hence, we can assume N \leq 10^{21}, and if we get N \gt 10^{21}, we replace N by 10^{21}
Classical Digit DP
This problem is like any other digit dp problem, we need to count some special numbers up to N. For this problem, we see that when checking a number for goodness, only the number of digits and the product of digits matter.
Classical digit DP suggests dividing all numbers in the range [0, N] into the following groups, assuming N has L digits.
- L-1 groups, i-th group containing i-digit numbers. Calling this group of first type
- L groups, i-th groups containing L-digit numbers having first i-1 digits same as N and i-th digit must be smaller than i-th digit of N. Calling this group of second type
For example, for N = 3241, we can divide interval [0, 3241] as follows
- [0,9] containing one digit numbers
- [10, 99] containing two-digit numbers
- [100, 999] containing three-digit numbers
- [1000, 2999] containing four-digit numbers with first 0 digits same, and digit indexed 1 strictly smaller than the corresponding digit of N. This is further split into [1000, 1999] and [2000, 2999]
- [3000, 3199] containing four-digit numbers with first 1 digits same, and digit indexed 2 strictly smaller than the corresponding digit of N. This is further split into [3000, 3099] and [3100, 3199]
- [3200, 3239] containing four digit numbers with first 2 digits same, and digit indexed 3 strictly smaller than corresponding digit of N. This is futher split into [3200, 3209], [3210, 3219], [3220, 3229] and [3230, 3239]
- [3240, 3240] containing four-digit numbers with first 3 digits same, and digit indexed 4 strictly smaller than the corresponding digit of N
- [3241, 3241] Interval containing N.
We can see that no two groups have a non-empty intersection and the union of all groups is [0, 3241], hence we can aim to calculate the number of good integers in each group.
The special feature of this partitioning is that groups
- For the first type is nothing but the number of d-digit numbers with digit product \geq d!
- For groups of the second type, we can see that the first d digits of all integers in some interval are the same, and for the rest, L-d digits can be chosen in any way independently.
Let’s say product of first d digits is X. So the product of remaining L-d integers must be Y such that \displaystyle X*Y \geq L! \implies Y \geq \left\lceil \frac{L!}{X} \right\rceil
So now, the problem boils down to computing the number of d-digit integers with digit product \geq v quickly, which shall be used to compute the number of good numbers in each of the group. Let’s denote f(d, v) as the number of d-digit numbers with digit product \geq v
Number of distinct digit products
Considering numbers like 246, 264, 426, 462, 624, 642, 168, 186, \ldots, 238, 443 and many more, we see that they all have digit product 48 and have the same number of digits. Either they are all valid, or they are all invalid since we only care about the number of digits and the digit product. It may be possible that there are far fewer values v such that there’s a number with digit product v.
Simply, we can see that the product can have only 2, 3, 5 and 7 as its prime factors as digits are in range 1 \leq d_i \leq 9 , where d_i denote i-th digit of N. So all such v which can be a digit product can be written as v = 2^p * 3^q * 5^r * 7^s where p, q, r, s \geq 0.
Additionally, there are number of constraints, such that \lceil p/3 \rceil + \lceil q/2 \rceil + r+s \leq L. This severely restricts the number of distinct digit products possible. We can actually bound the number of such integers by O(L^4), but the proof is beyond the scope of this editorial.
By running simulation, there are a total of 64009 distinct values of v if considering 21 digit numbers.
Let’s maintain mapping ((d, v), x) representing that there are x d-digit numbers having digit product v. We start with tuple ((0, 1), 1) representing empty number, and try appending digits from 1 to 9. Specifically, tuple (d,v) contributes x numbers to tuple (d+1, v*d_i), as for each of the x d-digit numbers with digit product v, we can append d_i at the end to obtain d+1 digit numbers with digit product d_i.
Hence, we can consider tuples in increasing order of d, and for mapping ((d, v), x), add x to tuple (d+1, v*d_i) for each 1 \leq d_i \leq 9.
Now, We need to answer query f(d, v) quickly. Let’s subdivide all tuples by d into d lists, and sort each list by v. Now we need to compute the suffix sum of frequencies, the number of d-digit numbers with product \geq v which can be done by looping over the list in reverse order and maintaining cumulative frequency.
Lastly, to answer f(d, v) quickly, we can use binary search on the list containing d-digit numbers.
Notes
- It might be useful to use 128-bit integers in C++ or Use Python (as I did). BigInteger in java is quite slow.
- Digit 0 didn’t need to be considered as that would make the digit product 0 immediately, making it a non-good number.
TIME COMPLEXITY
The time complexity would be O(10*L^4 + T*log(L^4)) where L = 22
SOLUTIONS
Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include<iostream>
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
#include<map>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
//=========================FOR __int128=======================//
template<class integer>
inline integer to_int(const string& s, size_t* idx = 0, int base = 10) {
size_t n = s.size(), i = idx ? *idx : 0; bool sign = false; integer x = 0;
if (s[i] == '-')
++i, sign = true;
function<int(char)> char_to_digit = [&](char c) {
static const int d[] = {'a'-10,'0'};
return tolower(c)-d[isdigit(c)]; };
while (i < n)
x *= base, x += char_to_digit(s[i++]);
if (idx)
*idx = i;
return sign ? -x : x; }
template<class integer>
inline string to_string(integer x, int base = 10) {
bool sign = false; string s;
if (x < 0)
x = -x, sign = true;
function<char(int)> digit_to_char = [](int d) {
static const char c[] = {'a'-10,'0'};
return c[d < 10]+d; };
do
s += digit_to_char(x%base), x /= base;
while (x > 0);
if (sign)
s += '-';
reverse(s.begin(),s.end());
return s; }
template<class integer>
inline istream& read(istream& is, integer& x) {
string s; is >> s, x = to_int<integer>(s); return is; }
template<class integer>
inline ostream& write(ostream& os, integer x) { return os << to_string(x); }
using lll = signed __int128;
using ulll = unsigned __int128;
inline istream& operator>>(istream& is, lll &x) { return read(is,x); }
inline istream& operator>>(istream& is, ulll &x) { return read(is,x); }
inline ostream& operator<<(ostream& os, lll x) { return write(os,x); }
inline ostream& operator<<(ostream& os, ulll x) { return write(os,x); }
//=========================ENDS HERE========================//
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<tuple<int,int,int>> vti3;
int mod1=(1e9+7);
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
//#define ll long long
#define pob pop_back
#define mii map<int,int>
#define si second
#define fi first
#define deb(i) cout<<"yes "<<i<<"\n"
#define mp make_pair
#define msi map<string,int>
#define musi unorderd_map<string,int>
#define test_n LL N; cin>>N; while(N--)
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
string str;
int n;
int possp[4]={2,3,5,7};
int maxprimep[4]={87, 57, 38, 31}; //logbase2(1e26),logbase3(1e26),logbase5(1e26),logbase7(1e26) Msximum power of prime in product
int primeFact[10][4] = { {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}, {0, 1, 0, 0}, {2, 0, 0, 0}, {0, 0, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}, {3, 0, 0, 0}, {0, 2, 0, 0}};
int num[87][57][38][31]; //stores list of products like as cordinate compression.
/*
No of different products if we have L digits is ((L+1)(L+2)/2)^2
*/
vector<pair<lll,int>> prodsortMap; //44100 for 1e18 //549081 for 1e36 //164836 for 1e26
vector<lll> prodsortMap_copy;
double maximum_product_possible; //maximum priduct possible in logbase10 form
lll otherProductmax; //maximum product possible in __int128 for each testcase for finding upper_bound and calculating using suffix sums
vector<lll> ppower[4]; //storing power of prime like ppower[0][2]=2^2=4
lll suffix_sum[26][242900]; //for every length of digits 1 to 25, stores the suffix sum for dp num_digitPROD.
lll neg_val=-1e9;
lll maxiProFactor[4]={ neg_val, neg_val, neg_val,neg_val};
lll maxiProFactor_val=-1e9;
lll dp[26][2]; //dp for calculating the final ans;
lll prod123[26]; //stores factorial in __int128
lll pprod9[26]; //stores power of 9
lll num_digitPROD[26][242900]; //dp num_digitPRDO[K][P] stores the number of numbers having K digits and P as product of digits.
bool B_num_digitPROD[26][242900]; //visited array for num_digit_PROD
//================Recursive dp for calculating num_digitPROD=====================//
inline lll func(int n, int a, int b, int c, int d){
if (n==0) return (!a && !b && !c && !d);
if (a < 0 || b < 0 || c < 0 || d < 0) return 0;
int j, k, h = num[a][b][c][d];
if (B_num_digitPROD[n][h]!=false) return num_digitPROD[n][h];
lll res = 0;
FOR(j,1,10){
res += func(n - 1, a - primeFact[j][0], b - primeFact[j][1], c - primeFact[j][2], d - primeFact[j][3]);
}
B_num_digitPROD[n][h] = true;
return (num_digitPROD[n][h] = res);
}
//==================ENDS HERE=================//
//===================function for generating all the products of digits of numbers less than 1e26,===================//
//=====================and count of such distinct products is very less==============================================//
inline void Precalculate(){
lll i, j, k, l, d, c = 0;
const double lg2 = log10(2.0), lg3 = log10(3.0), lg5 = log10(5.0), lg7 = log10(7.0);
lll value1;
double value;
for (i = 0; i < maxprimep[0]; i++){
for (j = 0; j < maxprimep[1]; j++){
for (k = 0; k < maxprimep[2]; k++){
for (l = 0; l < maxprimep[3]; l++){
value=((lg2 * i) + (lg3 * j) + (lg5 * k) + (lg7 * l));
if (value > maximum_product_possible ) break; //break if product is largeer than maximum possible product defined by us.
value1=ppower[0][i]* ppower[1][j] * ppower[2][k] * ppower[3][l];
num[i][j][k][l] = c; //just like coordinate compression we are assigning a integer to a product.
prodsortMap.pb({value1,c}); // passing the values of product in a map with associated integer to the product.
prodsortMap_copy.pb(value1); //paasing the values of prodicts in a copy map for easy lower_bound upper_bound operation.
maxiProFactor[0]=max(maxiProFactor[0],i); //taking maximum power each of 2,3,5,7 among every valid product
maxiProFactor[1]=max(maxiProFactor[1],j);
maxiProFactor[2]=max(maxiProFactor[2],k);
maxiProFactor[3]=max(maxiProFactor[3],l);
c++;
}
}
}
}
}
//=======function for psuedo digit-dp, for calculating the final answer incoporating lower_bounds and upper_bounds=======//
inline lll fun(lll pos,bool tight,lll pre_prod){
if(dp[pos][tight]!=-1){ return dp[pos][tight];}
if(pos==str.length()){
if(pre_prod>=prod123[n]){return 1;}
return 0;
}
int upper_bound1= (tight)?(str[pos]-'0'):9;
lll ans=0;
FOR(x,0,upper_bound1+1){
if(x==0){
lll index=lower_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),prod123[n-1-pos])-prodsortMap_copy.begin(); //the index in prodsortMap_copy after which evey product is larger than factorial of (n-1-pos)
lll index_last=upper_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),otherProductmax)-prodsortMap_copy.begin(); //the index in prodsortMap_copy after which evey product is larger than maximum product possible
ans= ans+ suffix_sum[n-1-pos][index]-suffix_sum[n-1-pos][index_last]; //incrementing ans using suffix sums of num_digitPROD[len][product_number]
if(x==upper_bound1){ //incrementing further if 0 is preseint in the original number given
FOR(pos_C,pos+1,n){
lll index=lower_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),prod123[n-1-pos_C])-prodsortMap_copy.begin();
lll index_last=upper_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),otherProductmax)-prodsortMap_copy.begin();
ans= ans+ suffix_sum[n-1-pos_C][index]-suffix_sum[n-1-pos_C][index_last];
}
}
continue;
}
else if(x!=upper_bound1){ //if x is not equal to upper_bound
lll key= ceil(double((double(prod123[n]))/(double(pre_prod*x))));
lll index=lower_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),key)-prodsortMap_copy.begin();
lll index_last=upper_bound(prodsortMap_copy.begin(),prodsortMap_copy.end(),otherProductmax)-prodsortMap_copy.begin();
ans= ans+ suffix_sum[n-1-pos][index]-suffix_sum[n-1-pos][index_last];
if(pos==n-1){ if(prod123[n]<=pre_prod*x){ ans++; } }
continue;
}
ans=(ans+ fun(pos+1, tight&&(x==upper_bound1),pre_prod*x ) );
}
return dp[pos][tight]=ans;
}
//================================================//
int main(){
fastio;
//freopen("output_rand.txt", "r", stdin);
//freopen("output_VER.txt", "w", stdout);
//clock_t start,end;
//start=clock();
/*
since 22!>9^22, so every number higher than = 1e22 will give same answer which turned out as 2121793450243
btw in program I calculated for 1e24
*/
maximum_product_possible=double((double(24))*(log10(9)));
lll prod=1;
lll prod9=1;
FOR(i,1,26){
prod*=i;
prod9*=9;
prod123[i]=prod;
pprod9[i]=prod9;
}
FOR(i,0,4){
FOR(j,0,maxprimep[i]+1){
lll tmp=pow(possp[i],j);
ppower[i].pb(tmp);
}
}
memset(B_num_digitPROD,false,sizeof(B_num_digitPROD));
memset(num_digitPROD,0,sizeof(num_digitPROD));
memset(num,-1,sizeof(num));
memset(suffix_sum,0,sizeof(suffix_sum));
Precalculate();
sort(prodsortMap.begin(),prodsortMap.end()); //sorting the map based on product values.
sort(prodsortMap_copy.begin(),prodsortMap_copy.end()); //again sorting based on product values.
//func(n,maxiProFactor[0],maxiProFactor[1],maxiProFactor[2],maxiProFactor[3]);
for(int i=24;i>=0;i--){
FOR(j,0,maxiProFactor[0]+1){
FOR(k,0,maxiProFactor[1]+1){
FOR(l,0,maxiProFactor[2]+1){
FOR(m,0,maxiProFactor[3]+1){
if(num[j][k][l][m]!=-1){
func(i,j,k,l,m);}
}
}
}
}
}
FOR(len,1,25){ lll sumi=0;
for(int i=prodsortMap.size()-1;i>=0;i--){ //calculating the suffix sum for all dp values num_digitPROD
sumi+=num_digitPROD[len][prodsortMap[i].si]; suffix_sum[len][i]=sumi;
}
}
test_n{
cin>>str;
n=str.length();
if(n>=23){
lll maximum_possible_answer=2121793450243;
cout<<maximum_possible_answer<<"\n";
continue;
}
otherProductmax=1;
FOR(i,0,n){
int d= str[i]-'0';
otherProductmax= otherProductmax * d;
// cout<<"p "<<otherProductmax<<"\n";
}
otherProductmax=max(otherProductmax,pprod9[n-1]);
otherProductmax=otherProductmax+1e9;
// cout<<" o "<<otherProductmax<<"\n";
maximum_product_possible=0;
FOR(i,0,n){
int c=str[i]-'0';
if(c==0){ maximum_product_possible=0; break;}
maximum_product_possible+=log10(c);
}
double mtmp= ((double(n-1))*log10(9));
// cout<<n-1<<" "<<fixed<<setprecision(12)<<log10(9)<<" "<<mtmp<<"\n";
if(mtmp>maximum_product_possible){ maximum_product_possible=mtmp;}
maximum_product_possible+=0.00000000000000001;
//cout<<maximum_product_possible<<" maxo\n";
memset(dp, -1, sizeof(dp));
lll ansi=fun(0,1,1);
cout<<ansi<<"\n";
}
/*
end=clock();
double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by program is : " << fixed
<< time_taken << setprecision(5);
cout << " sec " <<"\n";
*/
return 0;}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#ifdef HOME
#include <windows.h>
#endif
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
struct TTMaLong {
uint64_t a1, a2;
static const uint64_t HMOD = 1'000'000ULL;
static const uint64_t MOD = 1'000'000'000'000ULL;
TTMaLong(): a1(0), a2(0) {}
TTMaLong(uint64_t x) : a1(0), a2(x) {}
TTMaLong(uint64_t x, uint64_t y) : a1(x), a2(y) {}
TTMaLong(const TTMaLong& t) : a1(t.a1), a2(t.a2) {}
TTMaLong& operator=(const TTMaLong& t) = default;
bool operator<(const TTMaLong& o) const {
return std::tie(a1, a2) < std::tie(o.a1, o.a2);
}
bool operator==(const TTMaLong& o) const {
return std::tie(a1, a2) == std::tie(o.a1, o.a2);
}
void Normalize() {
if (a2 > MOD)
{
a1 += a2 / MOD;
a2 %= MOD;
}
}
TTMaLong& operator+=(const TTMaLong& t) {
a1 += t.a1;
a2 += t.a2;
Normalize();
return *this;
}
TTMaLong& operator-=(const TTMaLong& t) {
a1 -= t.a1;
a2 -= t.a2;
Normalize();
return *this;
}
TTMaLong& operator*=(uint64_t t) {
assert(t < 500);
a1 *= t;
a2 *= t;
Normalize();
return *this;
}
TTMaLong& operator*=(const TTMaLong& o) {
assert(a1 == 0 || o.a1 == 0);
a1 = a1 * o.a2 + a2 * o.a1;
//split
uint64_t a21 = a2 / HMOD;
uint64_t a22 = a2 % HMOD;
uint64_t oa21 = o.a2 / HMOD;
uint64_t oa22 = o.a2 % HMOD;
a1 += a21 * oa21;
a2 = (a22 * oa21 + a21 * oa22) * HMOD + oa22 * a22;
Normalize();
return *this;
}
TTMaLong operator+(const TTMaLong& t) const {
return TTMaLong(*this) += t;
}
TTMaLong operator-(const TTMaLong& t) const {
return TTMaLong(*this) -= t;
}
TTMaLong operator*(uint64_t t) const {
return TTMaLong(*this) *= t;
}
TTMaLong operator*(const TTMaLong& t) const {
return TTMaLong(*this) *= t;
}
bool isLarger(const TTMaLong& a, const TTMaLong& b) const
{//this * a < b
TTMaLong prod = a * (*this);
return a < b;
}
};
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
ios::sync_with_stdio(false);
const uint32_t maxD = 23;
vector<TTMaLong> fact(maxD);
fact[0] = TTMaLong(1);
fore(i,1, 22)
{
fact[i] = fact[i - 1] * i;
}
vector<map<TTMaLong, uint64_t>> alll(maxD);
fore(d, 1, 9)
{
alll[1][TTMaLong(d)] = 1;
}
fore(i, 2, maxD-1)
{
const auto& prev = alll[i - 1];
auto& act = alll[i];
for (const auto& pi : prev)
{
const TTMaLong& pv = pi.first;
const uint64_t& cv = pi.second;
fore(j, 1, 9)
{
TTMaLong cand = pv * j;
act[cand] += cv;
}
}
}
vector<vector<pair<TTMaLong, uint64_t> > > prS(maxD);
fore(i, 1, maxD - 1)
{
const auto& act = alll[i];
prS.reserve(act.size());
for (const auto& ai : act)
{
const TTMaLong& av = ai.first;
const uint64_t& ac = ai.second;
prS[i].push_back(std::make_pair(av, ac));
}
//reverse(prS[i].begin(), prS[i].end());
uint64_t pr = 0;
ford(j , prS[i].size())
{
auto& ai = prS[i][j];
pr = pr + ai.second;
ai.second = pr;
}
}
vector<uint64_t> good(maxD);
fore(i, 1, maxD - 1)
{
const auto& act = prS[i];
const auto& actf = fact[i];
uint32_t mi = 0, mx = act.size() - 1;
while (mi < mx)
{
uint32_t md = (mi + mx) / 2;
if (act[md].first < actf)
{
mi = md + 1;
}
else
{
mx = md;
}
}
good[i] = act[mi].second;
}
int T;
cin >> T;
forn(tc, T)
{
std::string N;
cin >> N;
if (N.length() >= maxD)
{
N = string(maxD - 1, '9');
}
uint32_t NL = N.length();
uint64_t ans = 0;
forn(i, NL)
ans += good[i];
TTMaLong pp(1);
const auto& NF = fact[NL];
forn(i, NL)
{
int actV = N[i] - '0';
if(actV == 0)
break;
uint32_t rem = NL - i - 1;
fore(j, 1, actV - 1)
{
TTMaLong pj = pp * j;
if (rem == 0)
{
if (!(pj < NF))
++ans;
continue;
}
const auto& act = prS[rem];
//the good pj * act[x] >= NF
uint32_t mi = 0, mx = act.size() - 1;
while (mi < mx)
{
uint32_t md = (mi + mx) / 2;
if (act[md].first * pj < NF)
{
mi = md + 1;
}
else
{
mx = md;
}
}
if (!(act[mi].first * pj < NF))
{
ans += act[mi].second;
}
}
pp *= actV;
if (rem == 0)
{
if (!(pp < NF))
++ans;
}
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
import sys
D = 22
dp = [dict() for _ in range(D)]
dp[0][1] = 1
# Generating all digit products for each 1 <= d <= 24
for d in range(D-1):
for product, freq in dp[d].items():
for nxt in range(1, 10):
dp[d+1][product*nxt] = freq + dp[d+1].get(product*nxt, 0)
products, frequencies = [list() for _ in range(D)], [list() for _ in range(D)]
sum = 0
for d in range(D):
dp[d] = dict(sorted(dp[d].items()))
tot = 0
for freq in dp[d].values():
tot += freq
for prod, freq in dp[d].items():
x = dp[d][prod]
dp[d][prod] = tot
tot -= x
products[d], frequencies[d] = list(dp[d].keys()), list(dp[d].values())
sum += len(dp[d])
def countNumsGreater(d, target):
'''Returns the number of good numbers consisting of d digits and having digit product >= target'''
lo, hi = 0, len(products[d])-1
if products[d][hi] < target:
return 0
while lo < hi:
mid = (lo+hi)//2
if products[d][mid] >= target:
hi = mid
else:
lo = mid+1
return frequencies[d][hi]
def good(N):
'''Returns true if N is a good number'''
N = str(N)
fact, prod = 1, 1
for d in range(len(N)):
fact *= d+1
prod *= ord(N[d])-ord('0')
return prod >= fact
def brute(N):
'''Brute force way to calculate answer in O(N)'''
N = int(N)
ans = 0
for x in range(1, 1+N):
if good(x):
ans += 1
return ans
T = int(input())
MAX = 10**(D-1)
for _ in range(T):
N = int(input())
if N > MAX:
N = MAX
N = str(N)
ans, fact = 0, 1
# Counting good numbers with digits less than number of digits of N
for d in range(1, len(N)):
fact *= d
ans += countNumsGreater(d, fact)
fact *= len(N)
product = 1
for p in range(len(N)):
# Counting the numbers having first p digits same as N, next digit strictly smaller than pth digit in N
di = ord(N[p]) - ord('0')
if di == 0:
break
for digit in range(1, di):
# Fixing next digit to be strictly smaller than di,
tmpProd = product*digit
ans += countNumsGreater(len(N) - p - 1, (fact + tmpProd - 1) // tmpProd)
product *= di
if good(N):
ans += 1
sys.stdout.write(str(ans)+"\n")
Feel free to share your approach. Suggestions are welcomed as always. 