Strobogrammatic Number III - Practice Coding Problems

Strobogrammatic Number III - Problem

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Given two strings low and high that represent two integers where low <= high, return the number of strobogrammatic numbers in the range [low, high].

The digits that remain the same when rotated 180 degrees are: 0, 1, 6, 8, 9 where:

0 → 0
1 → 1
6 → 9
8 → 8
9 → 6

Input & Output

Example 1 — Small Range

$ Input: low = "50", high = "100"

› Output: 3

💡 Note: Strobogrammatic numbers in range [50,100] are: 69, 88, 96. Each looks the same when rotated 180°.

Example 2 — Single Digit Range

$ Input: low = "0", high = "9"

› Output: 3

💡 Note: Single digit strobogrammatic numbers are: 0, 1, 8. Numbers 2,3,4,5,6,7,9 don't look the same when rotated.

Example 3 — No Valid Numbers

$ Input: low = "20", high = "30"

› Output: 0

💡 Note: No strobogrammatic numbers exist between 20 and 30.

Constraints

1 ≤ low.length, high.length ≤ 15
low and high consist of only digits
low ≤ high
low and high do not contain any leading zeros except for zero itself

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given low="50" and high="100"

Check Numbers

Find numbers that look same when rotated 180°

Count Valid

Return count of strobogrammatic numbers in range

Key Takeaway

🎯 Key Insight: Generate valid strobogrammatic numbers recursively instead of checking every number in range

Asked in

G Google 15 f Facebook 12

The key insight is that only digits 0,1,6,8,9 can form strobogrammatic numbers, and we can generate them recursively by adding valid pairs to shorter numbers. The optimal approach uses backtracking to generate only valid strobogrammatic numbers rather than checking every number in the range. Time: O(5^L), Space: O(5^L) where L is the maximum length.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O((high-low) × L)	O(L)	Check every number in the range to see if it's strobogrammatic
Generate and Count	O(5^L)	O(5^L)	Generate all possible strobogrammatic numbers and count those in range

Brute Force — Algorithm Steps

Iterate from low to high
For each number, check if it's strobogrammatic by comparing with its rotated version
Count valid numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Range Check

Iterate through all numbers from low to high

Rotation Test

For each number, rotate 180° and compare

Count Valid

Increment counter for matching numbers

Code -

solution.c — C

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

int isStrobogrammatic(const char* numStr) {
    char mapping[10] = {0};
    mapping['0'] = '0';
    mapping['1'] = '1';
    mapping['6'] = '9';
    mapping['8'] = '8';
    mapping['9'] = '6';
    
    int len = strlen(numStr);
    char rotated[20] = {0};
    
    for (int i = len - 1; i >= 0; i--) {
        char c = numStr[i];
        if (c < '0' || c > '9' || mapping[c] == 0) {
            return 0;
        }
        rotated[len - 1 - i] = mapping[c];
    }
    rotated[len] = '\0';
    
    return strcmp(rotated, numStr) == 0;
}

int solution(const char* low, const char* high) {
    int count = 0;
    long long lowNum = atoll(low);
    long long highNum = atoll(high);
    
    for (long long num = lowNum; num <= highNum; num++) {
        char numStr[20];
        sprintf(numStr, "%lld", num);
        if (isStrobogrammatic(numStr)) {
            count++;
        }
    }
    return count;
}

int main() {
    char low[20], high[20];
    fgets(low, sizeof(low), stdin);
    fgets(high, sizeof(high), stdin);
    low[strcspn(low, "\n")] = 0;
    high[strcspn(high, "\n")] = 0;
    
    int result = solution(low, high);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((high-low) × L)

For each number in range, we check L digits where L is average length

✓ Linear Growth

Space Complexity

O(L)

Extra space for string conversion and rotation check

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

847 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