// 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)
}