Numbers With Repeated Digits - Practice Coding Problems

Numbers With Repeated Digits - Problem

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

For example, if n = 100, numbers like 11, 22, 33, 44, 55, 66, 77, 88, 99, 100 all have repeated digits.

Input & Output

Example 1 — Small Number

$ Input: n = 20

› Output: 1

💡 Note: Only number 11 has repeated digits in range [1, 20]

Example 2 — Medium Number

$ Input: n = 100

› Output: 10

💡 Note: Numbers 11, 22, 33, 44, 55, 66, 77, 88, 99, 100 all have repeated digits

Example 3 — Single Digit

$ Input: n = 5

› Output: 0

💡 Note: Numbers 1, 2, 3, 4, 5 all have unique digits (single digit numbers)

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 100

Process

Count numbers [1,100] with repeated digits

Output

Return count = 10

Key Takeaway

🎯 Key Insight: Count numbers without repeated digits using combinatorics, then subtract from total

Asked in

G Google 15 a Amazon 8 M Microsoft 5

The key insight is that it's easier to count numbers without repeated digits using combinatorics, then subtract from total n. Best approach uses mathematical permutations to count unique digit numbers efficiently. Time: O(d²), Space: O(d) where d is number of digits.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × d)	O(d)	Check each number from 1 to n for duplicate digits
Mathematical Approach	O(d²)	O(d)	Count numbers without repeated digits, then subtract from total

Brute Force — Algorithm Steps

Step 1: Iterate through all numbers from 1 to n
Step 2: For each number, check if it has repeated digits
Step 3: Count numbers with repeated digits

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Number

Go through 1, 2, 3, ..., n

Detect Duplicates

For each number, check if any digit repeats

Count Results

Sum up all numbers with repeated digits

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool hasRepeatedDigits(int num) {
    char s[20];
    sprintf(s, "%d", num);
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (s[i] == s[j]) {
                return true;
            }
        }
    }
    return false;
}

int solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (hasRepeatedDigits(i)) {
            count++;
        }
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × d)

Check each of n numbers, each with d digits to verify

✓ Linear Growth

Space Complexity

O(d)

Space to store digit frequency for each number

✓ Linear Space

25.0K Views

Medium Frequency

~35 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler