Chef and Digits of Large Numbers solution codechef

Chef and Digits of Large Numbers solution codechef

For Solution

Click Here!

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.

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 010≯1.
  • The digits present in the integer 2525 are 2,52,5. So the product of digits is (25)=10(2⋅5)=10 and 2!=22!=2. So 2525 will be counted in the answer because 10210≥2.
  • The digits present in the integer 1111 are 1,11,1. So the product of digits is (11)=1(1⋅1)=1 and 2!=22!=2. So 1111 will be not counted in the answer because 121≯2.
  • The digits present in the integer 157157 are 1,5,71,5,7. So the product of digits is (157)=35(1⋅5⋅7)=35 and 3!=63!=6. So 157157 will be counted in the answer because 35635≥6.

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

NoteK!K! represents the factorial of KK and K!=123(K1)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

  • 1T101451≤T≤10145
  • 0N101000≤N≤10100

Subtasks

Subtask #1 (10 points):

  • 1T2001≤T≤200
  • 0N1070≤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 =1412=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,1120,3020,3040,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 100100101,102,101,102, 103,104,105103,104,105106,107,108106,107,108109,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,170180,190180,190 because their product of digits is less than 3!=63!=6.
    So the answer is =19911029=159=199−1−10−29=159.

    For Solution

    Click Here!

Leave a Comment