Coding

Confusing Number II

Asked at

Media.net

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively.
When 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid. Note that 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: n = 20 Output: 6 Explanation: The confusing numbers are [6,9,10,16,18,19]. 6 converts to 9. 9 converts to 6. 10 converts to 01 which is just 1. 16 converts to 91. 18 converts to 81. 19 converts to 61.

Input: n = 100 Output: 19 Explanation: The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100]

Input: n = 150

1 <= n <= 109

cpp

class Solution {
public:
    int confusingNumberII(int n) {
        // User code goes here
       
    }
};

java

class Solution {
    public int confusingNumberII(int n) {
        // User code goes here
     
    }
}

python

class Solution:
    def confusingNumberII(self, n: int) -> int:
        # User code goes here

javascript

class Solution {
    confusingNumberII(n) {
        // User code goes here
     
    }
}

csharp

public class Solution
{
    public int ConfusingNumberII(int n)
    {
        // User code goes here
     
    }
}

func confusingNumberII(n int) int {

}

Stuck? Show a way to structure it+

01Generate numbers using only rotatable digits.
02Avoid leading zeroes and stop beyond n.
03Rotate generated digits in reverse order using the mapping.
04Count values whose rotation differs from the original.

Reference answer

Only digits 0, 1, 6, 8, and 9 can appear. Backtrack to build valid candidates up to n, avoiding a leading zero; for each candidate, rotate by reading digits right-to-left and mapping 0→0, 1→1, 6→9, 8→8, 9→6. Count it when the rotated result differs. The search explores far fewer values than all integers up to n; time is proportional to generated valid candidates. Do not count 0 or numbers that rotate to themselves, such as 11 and 88. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Complexity: For d digits, the digit DFS explores at most O(5^d) candidates and uses O(d) recursion space; rotation checking adds only O(d) work per completed candidate.

Then expect these follow-ups

How would you count strobogrammatic rather than confusing numbers?
Tests: definition contrast
How can digit DP handle much larger n?
Tests: digit DP

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question