Rotated Digits

Medium
1175.

Rotated Digits

Rotated Digits is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.

Turn every digit of a number upside down (rotate it by 180 degrees), one digit at a time, keeping the digits in place. Under that rotation 0, 1 and 8 stay themselves, 2 and 5 turn into each other, 6 and 9 turn into each other, and 3, 4 and 7 become unreadable.

A positive integer x is good when every one of its digits survives the rotation and the rotated number is different from x. For example 69 becomes 96 (good), 818 stays 818 (not good) and 47 cannot be rotated (not good).

Return how many integers in the range [1, n] are good.

Example 1

Input
n = 10
Output
4
Explanation
The good numbers are 2, 5, 6 and 9. The number 10 rotates to itself.

Example 2

Input
n = 1
Output
0

Example 3

Input
n = 25
Output
12
Explanation
2, 5, 6, 9, 12, 15, 16, 19, 20, 21, 22 and 25.

Constraints

  • 1 <= n <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var rotatedDigits = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rotated Digits — Solution in Python, Java & C++

Rotated Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Rotated Digits is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Turn every digit of a number upside down (rotate it by 180 degrees), one digit at a time, keeping the digits in place. Under that rotation 0, 1 and 8 stay themselves, 2 and 5 turn into each other, 6 and 9 turn into each other, and 3, 4 and 7 become unreadable.

A positive integer x is good when every one of its digits survives the rotation and the rotated number is different from x. For example 69 becomes 96 (good), 818 stays 818 (not good) and 47 cannot be rotated (not good).

Return how many integers in the range [1, n] are good.

Example 1

Input: n = 10
Output: 4
Explanation: The good numbers are 2, 5, 6 and 9. The number 10 rotates to itself.

Example 2

Input: n = 1
Output: 0

Example 3

Input: n = 25
Output: 12
Explanation: 2, 5, 6, 9, 12, 15, 16, 19, 20, 21, 22 and 25.

Constraints

  • 1 <= n <= 10^4

Hints for Rotated Digits

  1. Hint 1

    A number is good when it uses no digit from {3, 4, 7} and uses at least one digit from {2, 5, 6, 9}.

  2. Hint 2

    Checking every number up to n digit by digit already works for these limits.

  3. Hint 3

    Faster: count the numbers up to n built only from {0,1,2,5,6,8,9}, then subtract those built only from {0,1,8} — a digit-by-digit walk over n counts each set in O(digits).

How to solve Rotated Digits

A number is good exactly when all its digits lie in {0,1,2,5,6,8,9} and not all of them lie in {0,1,8}. So the answer is (numbers in [0, n] using only the seven rotatable digits) minus (numbers in [0, n] using only the three self-rotating digits) — both counts include 0, which cancels.

Approach

  1. Write count(n, D) = how many integers in [0, n] have every digit in the set D (with leading zeros allowed, since 0 is in both sets).
  2. Walk the digits of n from the most significant. At a position with digit d and p positions to its right, every digit of D below d can be placed here followed by any of |D|^p tails: add (digits of D below d) * |D|^p.
  3. If d itself is not in D, stop — no number with this prefix can continue; otherwise move to the next digit.
  4. If the walk passes every digit, n itself qualifies: add 1.
  5. Return count(n, {0,1,2,5,6,8,9}) - count(n, {0,1,8}).

Why it works

The walk is the standard way to count numbers below a bound: every number < n agrees with n on some prefix and is smaller at the first differing position, and each such (prefix, smaller digit) pair is counted once with all its free tails. Numbers made only of {0,1,8} rotate to themselves and are exactly the rotatable numbers that are not good, so the difference counts the good ones.

Complexity

  • Time — O(log n)
  • Space — O(log n)

Pitfalls

  • A number that rotates to itself (like 1, 8 or 808) is not good even though it is rotatable.
  • Rotation acts per digit; do not reverse the digit order — the question only asks whether the result differs, and it differs exactly when a digit from {2,5,6,9} is present.
  • The brute-force check of every number is fine for n <= 10^4; the counting walk is what scales.

Reference solution

Python

def rotatedDigits(n: int) -> int:
    return _rd_count(n, {0, 1, 2, 5, 6, 8, 9}) - _rd_count(n, {0, 1, 8})

def _rd_count(n: int, allowed: set) -> int:
    digits = [int(c) for c in str(n)]
    k = len(digits)
    res = 0
    for i, d in enumerate(digits):
        smaller = sum(1 for a in allowed if a < d)
        res += smaller * len(allowed) ** (k - 1 - i)
        if d not in allowed:
            return res
    return res + 1

Java

static int rdCount(int n, int mask, int m) {
    int[] digs = new int[12];
    int k = 0;
    while (n > 0) { digs[k++] = n % 10; n /= 10; }
    int res = 0;
    for (int i = k - 1; i >= 0; i--) {
        int d = digs[i];
        int smaller = 0;
        for (int a = 0; a < d; a++) if (((mask >> a) & 1) == 1) smaller++;
        int p = 1;
        for (int t = 0; t < i; t++) p *= m;
        res += smaller * p;
        if (((mask >> d) & 1) == 0) return res;
    }
    return res + 1;
}

public static int rotatedDigits(int n) {
    // 871 = digits {0,1,2,5,6,8,9}; 259 = digits {0,1,8}
    return rdCount(n, 871, 7) - rdCount(n, 259, 3);
}

C++

int rdCount(int n, int mask, int m) {
    int digs[12];
    int k = 0;
    while (n > 0) { digs[k++] = n % 10; n /= 10; }
    int res = 0;
    for (int i = k - 1; i >= 0; i--) {
        int d = digs[i];
        int smaller = 0;
        for (int a = 0; a < d; a++) if ((mask >> a) & 1) smaller++;
        int p = 1;
        for (int t = 0; t < i; t++) p *= m;
        res += smaller * p;
        if (((mask >> d) & 1) == 0) return res;
    }
    return res + 1;
}

int rotatedDigits(int n) {
    // 871 = digits {0,1,2,5,6,8,9}; 259 = digits {0,1,8}
    return rdCount(n, 871, 7) - rdCount(n, 259, 3);
}

JavaScript

var rotatedDigits = function(n) {
    // 871 = digits {0,1,2,5,6,8,9}; 259 = digits {0,1,8}
    return rdCount(n, 871, 7) - rdCount(n, 259, 3);
};

var rdCount = function(n, mask, m) {
    var digs = [];
    while (n > 0) { digs.push(n % 10); n = Math.floor(n / 10); }
    var res = 0;
    for (var i = digs.length - 1; i >= 0; i--) {
        var d = digs[i];
        var smaller = 0;
        for (var a = 0; a < d; a++) if ((mask >> a) & 1) smaller++;
        var p = 1;
        for (var t = 0; t < i; t++) p *= m;
        res += smaller * p;
        if (((mask >> d) & 1) === 0) return res;
    }
    return res + 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming