颠倒它们时仍然是有效数字的数字

Question

1到n之间的数字是多少（当n是一个非常大的数字时），如果你颠倒了数字，你会得到一个不等于它自己的有效数字？

颠倒它们时的有效数字仍然有效：

[0,1,6,8,9] => [0,1,9,8,6]

翻转数字的示例：

989 => 686
981 => 186

回答主要问题的例子：如果你有n = 10，答案是3.这三个数字是：

• 6（因为9！= 6）
• 9（因为6！= 9）
• 10（因为10！= 01））

我尝试的是天真的方式：迭代数字1..n并检查每个数字，但是当n是一个很大的数字时，这是无效的。

Answer 1

尝试生成并计算所有可能的数字，这些数字在翻转后有效（在翻转后将是相同的数字）递归。

这是我的C ++实现：

int countValidFlippedNumber(int left, int right, string& str, const int n, bool isLessThanN) {
    if(left > right) {
        if(isLessThanN) {
            return 1;
        }
        int x = atoi(str.c_str());
        if(x <= n)
            return 1;

        return 0;
    }
    int count = 0;

    if((left == 0 and left == right) or left > 0) {
        str[left] = str[right] = '0';
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);
    }

    str[left] = str[right] = '1';
    count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);
    str[left] = str[right] = '8';
    count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);

    if(left < right) {
        str[left] = '6'; str[right] = '9';
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);

        swap(str[left], str[right]); // str[left] = '9'; str[right] = '6'; 
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);    
    }
    return count;
}

int validFlippedNumber(int n) {
    int len = to_string(n).length();
    int result = 0;
    string str;
    for(int i = 1; i < len; i++) {
        str.resize(i);
        result += countValidFlippedNumber(0, i - 1, str, n, true);
    }
    str.resize(len);
    result += countValidFlippedNumber(0, len - 1, str, n, false);
    return result;
}