Abstract / Summary

Count how many numbers can be rotated to form valid digits and must change during rotation.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (200k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Solution class implements a method rotatedDigits that counts how many numbers from 1 up to a given limit n remain valid after each digit is rotated 180 degrees on a seven-segment display. A number is considered good if every digit can be rotated into another digit and at least one digit changes to a different value after rotation. The implementation follows a straightforward brute-force strategy: it iterates through the entire range, checks each integer with a helper function, and aggregates the results.

Core Logic

Helper Function good

The nested function good determines whether a single integer satisfies the rotation criteria.

def good(n):  # 1 = True, 0 = False
    modified = 0
    for c in str(n):
        # cannot rotate
        if c in ["3", "4", "7"]:
            return 0
        # at least one digit must alter the result
        if c in ["2", "5", "6", "9"]:
            modified = 1
    return modified

The function converts the integer to a string and examines each character. If any character belongs to the set {3,4,7}, the number cannot be rotated at all, and the function returns 0 immediately. For digits that change after rotation (2,5,6,9), a flag modified is set to 1. Digits 0 and 1 are neutral-they rotate to themselves and do not affect the flag. After processing all characters, the function returns the flag, which is 1 only when at least one mutable digit was encountered and no illegal digit appeared.

Main Loop

The public method rotatedDigits aggregates the results of good across the full interval.

return sum(good(i) for i in range(1, n + 1))

A generator expression feeds each integer i to good, producing 1 for good numbers and 0 otherwise. The built-in sum then yields the total count.

Edge Cases Handled

The code explicitly handles numbers containing digits that are impossible to rotate (3, 4, 7). Encountering any of these digits triggers an early exit from good, ensuring that numbers such as 13 or 47 are correctly excluded.

Numbers composed solely of the neutral digits 0 and 1 (e.g., 10, 101) pass the illegal-digit test but never set the modified flag, so they are correctly classified as not good because no digit changes after rotation.

The lower bound of the range is 1, so the function never evaluates 0. This aligns with the problem definition, which typically excludes zero from the count.

When n is 1, the generator iterates over a single element, and good(1) returns 0, resulting in a final count of 0. This demonstrates correct handling of the minimal input size.

Performance Optimizations Present

Although the algorithm is conceptually simple, it incorporates a few micro-optimizations that reduce unnecessary work:

• Early termination on illegal digits - The return 0 statement inside the loop stops further character inspection as soon as an illegal digit is found. This prevents the function from scanning the remaining digits of numbers that are already disqualified, saving cycles especially for longer numbers with early illegal digits.

• Flag reuse instead of list construction - The function uses a single integer variable modified to track whether any mutable digit has been seen. This avoids building auxiliary data structures such as sets or lists, keeping memory usage minimal and reducing overhead from dynamic allocations.

• Generator expression for summation - By employing a generator expression inside sum, the code avoids constructing an intermediate list of results. Each call to good yields a value that is consumed immediately by sum, which is memory-efficient for large values of n.

• String conversion per number - Converting the integer to a string once per number allows digit inspection via simple character comparison, which is faster than repeatedly extracting digits using arithmetic operations (% and //). This choice leverages the highly optimized string handling in Python’s runtime.

These optimizations collectively keep the runtime modest for moderate input sizes, while the algorithm’s overall simplicity makes it easy to understand and maintain.

Imagine you have a box of magic blocks that have numbers written on them. Some of these numbers look exactly the same if you flip them upside down, like zero, one, and eight. Other numbers turn into different numbers when you spin them around, like two, five, six, and nine. But there are a few grumpy numbers, like three, four, and seven, that just break if you try to flip them over.

The code works like a tiny robot that looks at every number from one up to a big number you pick. For each number, the robot checks all of its digits one by one. If it sees a three, four, or seven, it knows that number is broken and tosses it away. If it sees at least one number that changes into a different friend when flipped, it puts that number in a special prize pile because it counts as a good rotated digit. After checking every single number, the code counts how many magic numbers made it into the prize pile.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java				Python		TS
	WalkCCC	C++		Java				Python
	leetcode.ca	C++		Java				Python	Go	TS
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim					C
	everthis		JS
	JoshCrozier		JS
	keineahnung2345	C++
	Krazune					C
	lkwq007							Python
	lzl124631x	C++
	ruoru						Rust
	suxrobGM				C#
	varunu28			Java
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality