Chef and Digits of Large Numbers Solution

August Long Challenge Chef and Digits of Large Numbers

Chef and Digits of Large Numbers

Chef and Abhishek are two friends. Abhishek really appreciates Chef’s skills and wants to learn the secret formula behind Chef’s tasty dishes. Chef will tell his secret formula only to a competent person. So to check Abhishek’s competency, Chef asked him to solve the following problem.

Find the number of integers between 00 to NN (including 00 and NN) such that the product of digits of the integer is greater than or equal to K!K!, where KK is the number of digits present in the integer.

Also See: August Long Challenge 2021 Solutions

Example: Consider N=1000N=1000.

  • The only digit present in the integer 00 is 00. So the product of digit is also 00 and 1!=11!=1. So 00 will be not counted in the answer because 0≯10≯1.
  • The digits present in the integer 2525 are 2,52,5. So the product of digits is (2⋅5)=10(2⋅5)=10 and 2!=22!=2. So 2525 will be counted in the answer because 10≥210≥2.
  • The digits present in the integer 1111 are 1,11,1. So the product of digits is (1⋅1)=1(1⋅1)=1 and 2!=22!=2. So 1111 will be not counted in the answer because 1≯21≯2.
  • The digits present in the integer 157157 are 1,5,71,5,7. So the product of digits is (1⋅5⋅7)=35(1⋅5⋅7)=35 and 3!=63!=6. So 157157 will be counted in the answer because 35≥635≥6.

Since Abhishek is a lazy person, he wants your help to solve the problem.

Note: K!K! represents the factorial of KK and K!=1⋅2⋅3⋅…⋅(K−1)⋅KK!=1⋅2⋅3⋅…⋅(K−1)⋅K .

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains a single integer NN.

Output Format

For each test case, output in a single line the answer for given integer NN

Constraints

  • 1≤T≤101451≤T≤10145
  • 0≤N≤101000≤N≤10100

Subtasks

Subtask #1 (10 points):

  • 1≤T≤2001≤T≤200
  • 0≤N≤1070≤N≤107

Subtask #2 (90 points): Original constraints

Sample Input 1 

3
13
54
198

Sample Output 1 

11
48
159

Explanation

Test case 11: The only one-digit number that will not be included in the answer is 00. The two-digit numbers that will not be included in the answer are 10,1110,11 because their product of digits is less than 2!=22!=2. So the answer is =14−1−2=11=14−1−2=11.

Test case 33:

  • The one-digit number that will not be counted in the answer is 00.
  • The two-digit digit numbers that will not be counted in the answer are 10,1110,11, 20,3020,30, 40,50,60,40,50,60, 70,80,9070,80,90 because their product of digits is less than 2!=22!=2.
  • The three-digit numbers that will not be counted in the answer are 100100, 101,102,101,102, 103,104,105103,104,105, 106,107,108106,107,108, 109,110,111,109,110,111, 112,113,114,112,113,114, 115,120115,120,121,121, 122,130,131,122,130,131, 140,141,150,140,141,150, 151,160,170151,160,170, 180,190180,190 because their product of digits is less than 3!=63!=6.
    So the answer is =199−1−10−29=159=199−1−10−29=159.

Solution:

Program C++:

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
#include <bitset>
#include <complex>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define X first
#define Y second
#define bit(x) ((ll)1 << (x))
#define sqr(x) ((x)*(x))
#define EPS (1e-8)
#define INF 0x3f3f3f3f
#define maxN 100010
#define maxK 60
#define mx 10000010
#define ml 19
#define mod 1000000007

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

char s[ml];
ll po[ml], fac[ml], tct[ml];
vector <string> pats[ml];
int b[11];

ll calc_pattern (string s)
{
	int i, j, k, len = s.size();
	j = 1; k = 0; char ch = s[0];
	ll tot = 1;
	for (i = 1; i < len; i++)
	{
		if (s[i] == ch)
		{
			j++;
		}
		else
		{
			tot *= fac[j];
			ch = s[i];
			j = 1;
		}
	}
	tot *= fac[j];
	return fac[len] / tot;
}

void pattern (int n, ll mul, string s)
{
	int i, j, lv = s.size();
	
	if (n == lv)
	{
		return;
	}
	
	if (mul >= fac[lv])
	{
		pats[lv].push_back(s);
		tct[lv] += calc_pattern(s);
	}
	
	for (i = s[lv - 1] - '0'; i <= 9; i++)
	{
		if (mul * i * po[n - lv - 1] >= fac[n])
		{
			pattern(n, mul * i, s + (char)('0' + i));
		}
	}

}

void init ()
{
	int i, j;
		
	po[0] = 1; 
	fac[0] = 1;
	for (i = 1; i < ml; i++)
	{
		po[i] = po[i - 1] * 9;
		fac[i] = fac[i - 1] * i;
	}
	
	memset(tct, 0, sizeof tct);
	string s; 
	s.clear();
	for (i = 1; i <= 9; i++) pattern(ml, i, s + (char)('0' + i));
	
	for (i = 1; i < ml; i++)
	{
		tct[i] += tct[i - 1];
	}
}

ll cal (string s)
{
	int i, j, k, len = s.size();
	ll cats, rlt = 0;
	for (auto pp : pats[len])
	{
		memset(b, 0, sizeof b);
		for (i = 0; i < len; i++) b[pp[i] - '0']++;
		cats = 1;
		for (i = 1; i <= 9; i++) cats *= fac[b[i]];

		for (i = 0; i < len; i++)
		{
			for (j = 0; j < s[i] - '0'; j++)
			{
				if (b[j] == 0)
				{
					continue;
				}
				rlt += fac[len - i - 1] * b[j] / cats;
			}
			
			if (b[j] == 0)
			{
				break;
			}
			cats /= b[j]--;
		}
		if (i == len) rlt++;
	}
	return rlt;
}

ll answer (string s)
{
	int i, j, len = s.size();
	if (len >= 19) return 0;
	return tct[len - 1] + cal(s);
}

int main ()
{
	int tc, i, j;
	ll n;
	init();
	scanf("%d", &tc);
	while (tc--)
	{
		string s;
		cin >> s;
		cout << answer(s) << endl;
	}
}

Program Python:

import sys
import bisect

NN=27

pw=[[1]*NN for i in range(NN)]
fac, cnt, adj, sz=[1]*NN, [0]*NN, [[] for i in range(NN)], [0]*NN

def dfs(val,num,ed):
    if val==0 and num>0:return 0
    if val==0:
        if ed!=1:return 0
        N,M,v=0,1,1
        for i in range(10):
            N+=cnt[i]
            M*=fac[cnt[i]]
            v*=pw[i][cnt[i]]
        NUM=fac[N]//M
        adj[N].append([v,NUM])
        return 0
    
    if pw[val][num]<ed:return 0
    for i in range(num+1):
        v=pw[val][i]
        cnt[val]=i
        dfs(val-1,num-i,(ed+v-1)//v)

def CLC(u):
    adj[u]=sorted(adj[u])
    ed=0
    for i in range(1,len(adj[u])):
        if adj[u][i][0]==adj[u][ed][0]:adj[u][ed][1]+=adj[u][i][1]
        else :
            adj[u][ed+1]=adj[u][i]
            ed+=1
    sz[u]=ed+1
    for i in range(ed-1,-1,-1):adj[u][i][1]+=adj[u][i+1][1]

a=[0]*NN

def seg(u,V):
    if u==0:
        if V<2: return 1
        else :return 0
    it=bisect.bisect_left(adj[u],[V,0],lo=0,hi=sz[u])
    if it==sz[u]:return 0
    return adj[u][it][1]

def calc(n):
    L=0
    while n>0:
        a[L]=n%10
        L+=1
        n//=10

    ans=0
    for i in range(1,L):ans+=seg(i,fac[i])
    V=fac[L]
    for i in range(L-1,-1,-1):
        for j in range(1,a[i]):ans+=seg(i,(V+j-1)//j)
        if a[i]==0:break
        V=(V+a[i]-1)//a[i]
        if i==0:
            if V==1:ans+=1
    return ans

if __name__=='__main__':
    for i in range(NN):
        for j in range(1,NN):pw[i][j]=pw[i][j-1]*i
    
    for i in range(1,NN):fac[i]=fac[i-1]*i

    for i in range(1,NN):
        CNT=0
        if i > 10: dfs(9,i,fac[i])
        else : dfs(9, i, 1)
        CLC(i)

    t=int(input())
    for i in range(t):
        n=int(input())
        n=min(n,10**22-1)
        print(min(n,calc(n)))

Codechef Long Challenges

August Long Challenge 2021 Solutions

July Long Challenge 2021 Solutions

Leave a Comment