// 8765
// XXX
// XX
// X
// 1XXX ~ 7XXX
// 80XX ~ 86XX
// 870X ~ 875X
// 8760 ~ 8765
const hasRepeated = function (s) {
s = '' + s;
// return true
return s.length !== [...new Set(s.split(''))].length;
}
const permutation = function (n, k) {
let p = 1;
for (let i = 0; i < k; ++i) {
p *= (n - i);
}
return p;
}
// n = 2 calculates the non-repeated numbers in range [10, 99] (inclusive)
const nDigitNoRepeat = function (n) {
if (n === 1) return 9;
else return 9 * permutation(9, n - 1);
}
const numDupDigitsAtMostN = function (n) {
const ns = '' + n;
// console.log(ns);
const nsl = ns.length;
let r = n, prefix = 0;
for (let i = 1; i < nsl; i++) {
r -= nDigitNoRepeat(i);
}
// console.log(r);
for (let i = 0; i < nsl; i++) {
let start = (i ? 0 : 1);
for (let j = start; j < ns[i]; j++) {
// console.log(j,ns[i]);
if (hasRepeated(prefix * 10 + j)) continue;
if (i !== nsl - 1) r -= permutation(10 - i - 1, nsl - 1 - i);
else r -= 1;
}
prefix = prefix * 10 + parseInt(ns[i]);
}
// console.log(hasRepeated(n));
return r - !hasRepeated(n)
}