What is the time complexity of Rotated Digits?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Rotated Digits?

This problem uses Math, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Rotated Digits?

Insight 1: A number is invalid if it contains the digits 3, 4, or 7 because these digits do not have a valid rotated counterpart. Insight 2: A valid number is considered 'good' only if it contains at least one of the digits 2, 5, 6, or 9, as these digits change upon rotation.

Which companies ask LeetCode 788. Rotated Digits in interviews?

This problem is frequently asked at Arista Networks.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Rotated Digits - LeetCode 788 Solution

Q: How to solve Rotated Digits?

The provided code iterates through each number from 1 to 'n'. For each number, it converts it into a string to easily check for the presence of specific digits. It first checks if the string contains any invalid digits ('3', '4', or '7'). If it does, the number is skipped. If the number is valid (no invalid digits), it then checks if the string contains any of the 'good' digits ('2', '5', '6', or '9'). If it does, the count of 'good' numbers is incremented. Finally, the total count of 'good' numbers is returned.

Rotated Digits - Complete Solution Guide

Rotated Digits is LeetCode problem 788, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x . Each digit must be rotated - we cannot choose to leave it alone. A number is valid if each digit remains a digit after rotation. For example: 0 , 1 , and 8 rotate to themselves, 2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored), 6 and 9 rotate to each other, and the rest of the numbers do not ro

Detailed Explanation

The problem asks us to find the number of 'good' integers within a given range [1, n]. A 'good' integer is defined as one that, after rotating each digit individually by 180 degrees, becomes a valid number that is *different* from the original number. The rotations are as follows: 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other; and 3, 4, and 7 do not rotate to any digit and become invalid. The input is a single integer 'n', and the output is the count of 'good' numbers between 1 and 'n' (inclusive). The constraint is that 1 <= n <= 10^4.

Solution Approach

The provided code iterates through each number from 1 to 'n'. For each number, it converts it into a string to easily check for the presence of specific digits. It first checks if the string contains any invalid digits ('3', '4', or '7'). If it does, the number is skipped. If the number is valid (no invalid digits), it then checks if the string contains any of the 'good' digits ('2', '5', '6', or '9'). If it does, the count of 'good' numbers is incremented. Finally, the total count of 'good' numbers is returned.

Step-by-Step Algorithm

Step 1: Initialize a counter 'count' to 0. This counter will store the number of 'good' integers.
Step 2: Iterate through each number 'i' from 1 to 'n' (inclusive).
Step 3: Convert the number 'i' to a string 's'.
Step 4: Check if the string 's' contains any of the invalid digits '3', '4', or '7'. If it does, the number is not valid, so continue to the next iteration.
Step 5: If the string 's' does not contain any invalid digits, check if it contains at least one of the 'good' digits '2', '5', '6', or '9'.
Step 6: If the string 's' contains at least one 'good' digit, increment the counter 'count'.
Step 7: After iterating through all the numbers from 1 to 'n', return the value of 'count'.

Key Insights

Insight 1: A number is invalid if it contains the digits 3, 4, or 7 because these digits do not have a valid rotated counterpart.
Insight 2: A valid number is considered 'good' only if it contains at least one of the digits 2, 5, 6, or 9, as these digits change upon rotation.
Insight 3: The problem can be efficiently solved by iterating through each number in the given range and checking if it satisfies both validity and 'goodness' criteria.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Math, Dynamic Programming.

Companies

Asked at: Arista Networks.

Rotated Digits | LeetCode 788

Medium

Math Dynamic Programming

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int rotatedDigits(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            String s = String.valueOf(i);

            // A number is "good" if it is valid and different after rotation.
            // Validity means it does not contain any of '3', '4', '7'.
            // Being different means it contains at least one of '2', '5', '6', '9'.

            // First, check for invalid digits.
            if (s.contains("3") || s.contains("4") || s.contains("7")) {
                continue;
            }

            // If valid, check if it's different after rotation.
            if (s.contains("2") || s.contains("5") || s.contains("6") || s.contains("9")) {
                count++;
            }
        }
        return count;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 788: Rotated Digits - Detailed explanation and solution approaches.

Topics

Math Dynamic Programming

Companies

Arista Networks

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:788

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a counter 'count' to 0. This counter will store the number of 'good' integers.
2
Step 2: Iterate through each number 'i' from 1 to 'n' (inclusive).
3
Step 3: Convert the number 'i' to a string 's'.
4
Step 4: Check if the string 's' contains any of the invalid digits '3', '4', or '7'. If it does, the number is not valid, so continue to the next iteration.
5
Step 5: If the string 's' does not contain any invalid digits, check if it contains at least one of the 'good' digits '2', '5', '6', or '9'.
6
Step 6: If the string 's' contains at least one 'good' digit, increment the counter 'count'.
7
Step 7: After iterating through all the numbers from 1 to 'n', return the value of 'count'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because the code iterates from 1 to 'n'. Inside the loop, the string operations (contains/find) take time proportional to the number of digits, which grows logarithmically with 'n', making it a relatively minor factor. The space complexity is O(1) because we're only using a fixed number of variables regardless of how large 'n' gets.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dynamic Programming

We can use dynamic programming to solve this problem. Let dp[i] be a boolean value that indicates whether the number 'i' is a good number. The base cases are dp[0] = false, dp[1] = false, dp[2] = true, dp[5] = true, dp[6] = true, dp[8] = false, dp[9] = true. Then for i > 9, we can iterate through the digits of i and check their rotation value. It could be more performant for extremely large `n` if implemented carefully.

Time: O(n)Space: O(n)

Trade-offs: The dynamic programming approach has a higher space complexity O(n) compared to the iterative approach O(1). The DP approach may be faster for very large values of n due to optimized memoization but likely not for the given constraint of 1 <= n <= 10^4.

✨

Key Insights

1Insight 1: A number is invalid if it contains the digits 3, 4, or 7 because these digits do not have a valid rotated counterpart.
2Insight 2: A valid number is considered 'good' only if it contains at least one of the digits 2, 5, 6, or 9, as these digits change upon rotation.
3Insight 3: The problem can be efficiently solved by iterating through each number in the given range and checking if it satisfies both validity and 'goodness' criteria.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: n = 1. The expected output is 0, as '1' rotates to itself and doesn't satisfy the 'good' condition. The code correctly handles this, as '1' is valid but not 'different'.
Edge case 2: n = 10. The expected output is 4 (2, 5, 6, 9). The code iterates to 10, finds 1 and 10 are not 'good', and counts 2, 5, 6, and 9. The code correctly handles this case.
Edge case 3: n = 2. Output is 1 (only 2 is good). Code correctly outputs 1.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to check for *both* validity (no 3, 4, 7) and 'goodness' (at least one of 2, 5, 6, 9). Some might check only for validity or only for 'goodness'.

✗Common mistake 2: Not handling the edge cases correctly. For small values of 'n', it's easy to make off-by-one errors in the counting process.

✗Common mistake 3: Premature optimization. DP would be an overkill and less readable than the current approach.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: This problem demonstrates a basic form of pattern recognition and conditional checking, useful in data validation where you need to filter data based on specific criteria.

🏦Real-world scenario 2: The core logic of checking digits against a specific set can be applied in barcode or QR code scanners where certain digit combinations might indicate specific product types or error codes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Rotated Digits"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?