1012. Numbers With Repeated Digits

Description

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

 

Example 1:

Input: n = 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

Input: n = 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3:

Input: n = 1000
Output: 262

 

Constraints:

• 1 <= n <= 109

 

Solutions

Solution: Math

• Time complexity: O(logn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const numDupDigitsAtMostN = function (n) {
  const nums = `${n + 1}`.split('').map(Number);
  let result = 0;

  const specialCount = (count, digits) => {
    if (digits === 0) return 1;

    return specialCount(count, digits - 1) * (count - digits + 1);
  };

  for (let digits = 1; digits < nums.length; digits++) {
    result += 9 * specialCount(9, digits - 1);
  }

  const seen = new Set();

  for (let index = 0; index < nums.length; index++) {
    for (let num = index > 0 ? 0 : 1; num < nums[index]; num++) {
      if (seen.has(num)) continue;

      result += specialCount(9 - index, nums.length - index - 1);
    }

    if (seen.has(nums[index])) break;
    seen.add(nums[index]);
  }

  return n - result;
};