Skip to content

1088. Confusing Number II

  • Time: $O(5^{\log n})$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int confusingNumberII(int n) {
    return dfs(n, 0, 0, 1);
  }

 private:
  vector<pair<int, int>> digitToRotated{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};

  int dfs(int n, long num, long rotatedNum, long unit) {
    int ans = num != rotatedNum;
    // Add one more digit
    for (const auto& [digit, rotated] : digitToRotated) {
      if (digit == 0 && num == 0)
        continue;
      const long nextNum = num * 10 + digit;
      if (nextNum > n)
        break;
      ans += dfs(n, nextNum, rotated * unit + rotatedNum, unit * 10);
    }
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int confusingNumberII(int n) {
    return dfs(n, 0, 0, 1);
  }

  private int[][] digitToRotated = {{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};

  int dfs(int n, long num, long rotatedNum, long unit) {
    int ans = num == rotatedNum ? 0 : 1;
    // Add one more digit
    for (int[] pair : digitToRotated) {
      final int digit = pair[0];
      final int rotated = pair[1];
      if (digit == 0 && num == 0)
        continue;
      final long nextNum = num * 10 + digit;
      if (nextNum > n)
        break;
      ans += dfs(n, nextNum, rotated * unit + rotatedNum, unit * 10);
    }
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def confusingNumberII(self, n: int) -> int:
    digitToRotated = [(0, 0), (1, 1), (6, 9), (8, 8), (9, 6)]

    def dfs(num: int, rotatedNum: int, unit: int) -> int:
      ans = 0 if num == rotatedNum else 1
      # Add one more digit
      for digit, rotated in digitToRotated:
        if digit == 0 and num == 0:
          continue
        nextNum = num * 10 + digit
        if nextNum > n:
          break
        ans += dfs(nextNum, rotated * unit + rotatedNum, unit * 10)
      return ans

    return dfs(0, 0, 1)