Remove 9 - Practice Coding Problems

Remove 9 - Problem

Math Hard

Start from integer 1, remove any integer that contains the digit 9 such as 9, 19, 29, etc. Now, you will have a new integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, ...].

Given an integer n, return the nth (1-indexed) integer in the new sequence.

Note: The sequence is 1-indexed, meaning the first element is at position 1.

Input & Output

Example 1 — Basic Case

$ Input: n = 8

› Output: 10

💡 Note: The sequence without 9s is [1,2,3,4,5,6,7,8,10,11,...]. The 8th number is 10 (we skip 9).

Example 2 — Small Position

$ Input: n = 5

› Output: 6

💡 Note: The sequence is [1,2,3,4,5,6,7,8,10,...]. The 5th number is 6.

Example 3 — After Multiple 9s

$ Input: n = 18

› Output: 20

💡 Note: Sequence: [1,2,3,4,5,6,7,8,10,11,12,13,14,15,16,17,18,20,...]. 18th number is 20 (skip 9,19).

Constraints

1 ≤ n ≤ 8 × 10⁸

Visualization

Tap to expand

Understanding the Visualization

Original Sequence

Normal counting: 1,2,3,4,5,6,7,8,9,10,11,...

Remove 9s

Skip any number containing digit 9

New Sequence

Result: 1,2,3,4,5,6,7,8,10,11,...

Key Takeaway

🎯 Key Insight: The sequence without 9s is equivalent to base-9 counting mapped to digits 1-8

Asked in

G Google 15 a Amazon 10 f Facebook 8

The key insight is recognizing that numbers without digit 9 form a base-9 system using digits 1-8. Best approach is mathematical conversion: convert position n to base-9, then map each digit d to d+1. Time: O(log n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Base-9 Conversion	O(log n)	O(log n)	Convert position n to base-9, then map digits 0-8 to 1-9 (excluding 9)
Brute Force - Count and Skip	O(n × log(result))	O(1)	Count integers from 1, skip those containing digit 9, return nth valid number

Mathematical Base-9 Conversion — Algorithm Steps

Convert position n to base-9 representation
Map each base-9 digit d to d+1
Combine digits to form the result

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Base-9

Position 8 → 0-indexed 7 → base-9: 7

Map Digits

Map base-9 digit 7 to 8 (add 1)

Build Result

Result is 8 in decimal

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    int result = 0;
    int base = 1;
    
    // Convert n to base-9, but map digits 0-8 to 1-8
    while (n > 0) {
        n -= 1; // Convert to 0-indexed
        int digit = n % 9; // Get base-9 digit (0-8)
        result = (digit + 1) * base + result; // Map to 1-8
        base *= 10;
        n /= 9;
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Converting n to base-9 requires O(log n) divisions and digit operations

⚡ Linearithmic

Space Complexity

O(log n)

Need to store base-9 digits, which is at most O(log n) digits

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Mathematical Base-9 Conversion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler