Confusing Number II - Practice Coding Problems

Confusing Number II - Problem

Math Backtracking Hard

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.

We can rotate digits of a number by 180 degrees to form new digits:

When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively
When 2, 3, 4, 5, 7 are rotated 180 degrees, they become invalid

Note: After rotating a number, we can ignore leading zeros. For example, after rotating 8000, we have 0008 which is considered as just 8.

Given an integer n, return the number of confusing numbers in the inclusive range [1, n].

Input & Output

Example 1 — Small Range

$ Input: n = 20

› Output: 6

💡 Note: Confusing numbers in [1,20]: 6→9, 9→6, 10→01=1, 16→91, 18→81, 19→61. Count = 6.

Example 2 — Single Digit

$ Input: n = 9

› Output: 2

💡 Note: Only 6→9 and 9→6 are confusing in range [1,9]. Numbers 0,1,8 rotate to themselves.

Example 3 — Edge Case

$ Input: n = 1

› Output: 0

💡 Note: Number 1 rotates to 1 (same), so it's not confusing. No confusing numbers in [1,1].

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Range

Check all numbers from 1 to n

Rotation Rules

0→0, 1→1, 6→9, 8→8, 9→6, others invalid

Count Different

Count numbers where rotation ≠ original

Key Takeaway

🎯 Key Insight: Only generate numbers using digits {0,1,6,8,9}, then count those where rotation differs from original

Asked in

G Google 15 f Facebook 8

The key insight is that only digits {0,1,6,8,9} can be rotated validly, and we only need to count numbers where the rotation differs from the original. The backtracking approach is optimal as it generates only valid candidates rather than checking all numbers. Time: O(5^d), Space: O(d) where d is the number of digits in n.

Common Approaches

Approach	Time	Space	Notes
✓ Check Every Number	O(n × d)	O(d)	Iterate through all numbers 1 to n and check if each is confusing
Backtracking Generation	O(5^d)	O(d)	Generate only valid numbers using backtracking with digits {0,1,6,8,9}

Check Every Number — Algorithm Steps

Iterate through numbers 1 to n
For each number, check if all digits are rotatable
Rotate the number and compare with original
Count numbers where rotation differs

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Number

Iterate through 1,2,3,...,n

Validate & Rotate

Check if digits are valid, then rotate

Count Different

Increment count if rotation differs

Code -

solution.c — C

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

char getRotation(char digit) {
    switch(digit) {
        case '0': return '0';
        case '1': return '1';
        case '6': return '9';
        case '8': return '8';
        case '9': return '6';
        default: return '\0';
    }
}

int isConfusing(int num) {
    char s[20], rotated[20];
    sprintf(s, "%d", num);
    int len = strlen(s);
    
    // Check if all digits are rotatable
    for (int i = 0; i < len; i++) {
        if (getRotation(s[i]) == '\0') {
            return 0;
        }
    }
    
    // Rotate the number
    for (int i = 0; i < len; i++) {
        rotated[i] = getRotation(s[len - 1 - i]);
    }
    rotated[len] = '\0';
    
    // Remove leading zeros
    int rotatedNum = atoi(rotated);
    sprintf(rotated, "%d", rotatedNum);
    
    // Check if different from original
    return strcmp(rotated, s) != 0;
}

int solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (isConfusing(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 n numbers, each with d digits to validate and rotate

✓ Linear Growth

Space Complexity

O(d)

Space to store digit string during rotation check

✓ Linear Space

23.0K Views

Medium Frequency

~35 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

Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler