Submission

PP---P----

Score: 30

User: Pera

Problemset: Strobogrammatic Numbers

Language: python

Time: 0.246 second

Submitted On: 2025-04-11 13:25:57

def find_strobogrammatic_in_range(low, high):
    strobogrammatic_pairs = [("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6")]

    def generate_strobogrammatic(n):
        if n == 0:
            return [""]
        if n == 1:
            return ["0", "1", "8"]

        middle_numbers = generate_strobogrammatic(n - 2)
        result = []
        for mid in middle_numbers:
            for pair in strobogrammatic_pairs:
                # Avoid leading zero for numbers longer than 1 digit
                if pair[0] != "0" or n != 1:
                    result.append(pair[0] + mid + pair[1])
        return result

    def count_strobogrammatic(low, high):
        low_num = int(low)
        high_num = int(high)
        count = 0
        
        low_len = len(low)
        high_len = len(high)

        for length in range(low_len, high_len + 1):
            nums = generate_strobogrammatic(length)
            for num_str in nums:
                # Handle cases where generated number might be out of range
                if len(num_str) == len(low) and int(num_str) < low_num:
                    continue
                if len(num_str) == len(high) and int(num_str) > high_num:
                    continue
                
                if low_num <= int(num_str) <= high_num:
                    count += 1
        return count

    return count_strobogrammatic(low, high)

def main():
    low: int = input()
    high: int = input()
    print(find_strobogrammatic_in_range(low, high))
    
main()