LeetCode Solutions

1088. Confusing Number II

Time: $O(5^{\log n})$

Space: $O(\log n)$

			

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;
  }
};
			

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;
  }
}
			

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)