Kata

Code a program that will count all the digits in the numbers 1 to n without timing out for large inputs.

• Requirement: Output in BigInt.

• 1 <= Input n <= 10^15

Examples:

(n) => total digits in numbers 1 to n

(9) => 9. There are 9 digits in the numbers 1 to 9.

(10) => 11. There are 11 digits in the numbers 1 to 10.

(15) => 21. There are 21 digits in the numbers 1 to 15.

Notes: Brute force methods like below will work up to about 10 to the 8th power but will fail at 10 to the 9th power, so be sure to develop an efficient algorithm. The brute force function below was useful to me for defining the problem more clearly, so I would know what to code to. So you may want to use something like that to help you get there. By the way with n = 10 to the 15th power my code returns the solution in about 0.1 milliseconds. So you can see memoization makes a huge difference.

function bruteForceDigits(n) {
 let myDigits = 0;
 for ( let x=1; x <= n; x++ )
   myDigits += String(x).length; 
 return myDigits; 
}

console.log( bruteForceDigits(75) ); // 141