Algorithm (Recursion)

1. The set of confusing numbers form a 6-ary tree implicitly. So we just need to fold it to count the total numbers. Fold is mostly $\texttt{dfs}$ in terms of trees. It’s more commonly known as backtracking.

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

class Solution {
 public:
  int confusingNumberII(int N) {
    using int64 = long long;

    const auto candidates = vector<int> {0, 1, 6, 8, 9};

    auto rotate = [](int i) {
      if (i == 0)
        return 0;
      else if (i == 1)
        return 1;
      else if (i == 6)
        return 9;
      else if (i == 8)
        return 8;
      else if (i == 9)
        return 6;
      else
        throw std::domain_error("non-rotatable");
    };

    auto eval = [](const vector<int>& num) {
      int acc = 0;
      for (const auto x : num)
        acc = (acc * 10) + x;
      return acc;
    };

    auto is_confusing = [&](int64 num) {
      const auto rotated = [&](int64 acc = 0) {
        auto num_copy = num;
        while (num_copy != 0) {
          acc = acc * 10 + rotate(num_copy % 10);
          num_copy /= 10;
        }
        return acc;
      }();

      return rotated != num;
    };

    auto solution = [&] {
      int acc = 0;
      auto count = rec([&](auto&&count, int64 num) -> void {
        if (num > N)
          return; 
        else {
          if (is_confusing(num))
            ++acc;
          for (const auto x : candidates) {
            if (num == 0 and x == 0)
              continue;
            else
              count(num * 10 + x);
          }
        }
      });
      return count(0), acc;
    }();

    return solution;
  }
};