Katkat
Back

Count three-digit numbers with distinct digits

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to count numbers satisfying digit-based constraints within a specific range using combinatorial logic or efficient iteration.

Problem Statement

Given an integer N, write a function count_distinct_three_digit(N) that returns the total count of numbers between 100 and N (inclusive) that consist of three distinct digits.

A number has distinct digits if no two digits in the number are the same (e.g., 123 is valid, but 121 and 100 are not).

Constraints

  • 100 <= N <= 999

Examples

Example 1: Input: N = 105 Output: 6 Explanation: The numbers are 102, 103, 104, 105. Wait, checking distinct digits: 102 (yes), 103 (yes), 104 (yes), 105 (yes). Total count is 4. (Note: 100, 101 are not distinct).

Example 2: Input: N = 120 Output: 17 Explanation: All numbers from 102 to 120, excluding those with repeating digits (like 110, 111, 112...119).

Hints

Hint 1

Since the range is small (only 900 possible candidates), consider whether a simple iteration with a helper function to check for distinct digits is efficient enough.

Hint 2

To check if a number has distinct digits, convert the number to a string or use modulo and division to extract digits into a set or boolean array.

Hint 3

If the range were much larger (e.g., N up to 10^9), you would need to use digit dynamic programming or combinatorial math instead of iteration.

Follow-up questions

  • How would your approach change if the range was significantly larger, such as 100 to 1,000,000,000?
  • Could you solve this using a combinatorial approach (calculating permutations) instead of iterating through every number?
  • How would you modify the function to count numbers with distinct digits that are also divisible by a specific integer K?