# Approach\nThis solution is fairly complex but it is able to count all the solutions very quickly by just counting permutations and no search.\n\nSuppose n is 54321 For each of the ranges 1..9, 10..99, 100..999, 1000..9999, 10000..54321 (one length at a time) we count up the number of confusing numbers in the range. Adding these gives the result.\n\nTo count up confusing numbers of a particular length, we count two things: 1. the number of numbers in the range made up only of valid flippable characters (`valid_digits`), and 2. the number of numbers in the range equal to their own flip (`flip_identical`). We subtract these to get the result.\n\nTo get these two counts, we carefully enumerate the number of valid possible values for each digit, and multiply these results. First, we further subdivide the ranges into some smaller ranges:\n\n[10000..54321] = [10000, 50000) + [50000, 54000) + [54000, 54300) + [54300, 54320) + [54320, 54321]\n\nFor each of these ranges, some digits are fixed (e.g. in [54000, 54300) the 5, 4 are fixed), some digits are constrained to be less than a certain value (e.g. third digit must be < 3), and the others are free to vary.\n\nIf the digit is fixed:\n\n1. If it cannot be flipped, there are no confusing numbers in range.\n2. If it is in middle position, and is not its own flip, there are no `flip_identical` values in range.\n3. If it is after the middle position, and is not the flip of the corresponding value on the other side, again there are no `flip_identical` values in range.\n\nIf the digit must be less than a certain value (or <= for the final closed interval):\n\n1. For `valid_digits`, just count up number of flippable valid digits less than the value. If before the middle, do same for `flip_identical`.\n2. If in the middle, for `flip_identical` count up number of flippable valid digits less than the value that are also their own flip.\n3. If after the middle, for `flip_identical`, the value must be the flip of its corresponding digit on the other side. If this value is less than the value, we\'re good, otherwise `flip_identical` is zero.\n\nFinally, if the digit is unconstrained:\n\n1. For `valid_digits` just multiply by 5 for 0, 1, 6, 8, 9. Same for `flip_identical` if before the middle digit.\n2. If looking at middle digit, `flip_identical` may choose any value that is its own flip (0, 1, 8) so multiply by 3.\n3. If after the middle, for `flip_identical` we must match the corresponding digit before the middle, so multiply by 1.\n\n# Complexity\n- Time complexity:\n$$O(\\log^3 n)$$ since there are two nested loops over the length of n, and the function is called once for each length up to length of n. In practice, it was so fast it got measured as 0 ms in submission, beating 100%.\n\n- Space complexity:\n$$O(\\log n)$$ to store string representation of n.\n\n# Code\n```\nclass Solution {\npublic:\n const int num_flippable_digits = 5;\n\n const int num_flippable_digits_no_change = 3;\n\n bool is_flippable(char c) {\n return c == \'0\' || c == \'1\' || c == \'6\' || c == \'8\' || c == \'9\';\n }\n\n bool is_flippable_no_change(char c) {\n return c == \'0\' || c == \'1\' || c == \'8\';\n }\n \n int less_flippable(char c, bool first_pos, bool last_pos) {\n int table[] = {\n /*0*/ 0,\n /*1*/ 1,\n /*2*/ 2,\n /*3*/ 2,\n /*4*/ 2,\n /*5*/ 2,\n /*6*/ 2,\n /*7*/ 3,\n /*8*/ 3,\n /*9*/ 4,\n /*all*/ 5,\n };\n if (last_pos) {\n return table[c - \'0\' + 1]; // Allow <= in last spot since n is inclusive\n }\n int result = table[c - \'0\'];\n if (first_pos) {\n return result - 1; // can\'t have zero in first position\n }\n return result;\n }\n\n int less_flippable_no_change(char c, bool first_pos, bool last_pos) {\n int table[] = {\n /*0*/ 0,\n /*1*/ 1,\n /*2*/ 2,\n /*3*/ 2,\n /*4*/ 2,\n /*5*/ 2,\n /*6*/ 2,\n /*7*/ 2,\n /*8*/ 2,\n /*9*/ 3,\n /*all*/ 3,\n };\n if (last_pos) {\n return table[c - \'0\' + 1]; // Allow <= in last spot since n is inclusive\n }\n int result = table[c - \'0\'];\n if (first_pos) {\n return result - 1; // can\'t have zero in first position\n }\n return result;\n }\n\n char flipped(char c) {\n if (c == \'6\') {\n return \'9\';\n } else if (c == \'9\') {\n return \'6\';\n } else {\n return c; // assuming is valid flippable\n }\n }\n\n // Count numbers from [100...0, n] where 100...0 has same number of digits as n\n int countConfusingNumbersOfMaxLength(int n) {\n string s = to_string(n);\n int count_with_valid_digits = 0; // count values <= n which are composed of flippable digits 0, 1, 6, 8, 9\n int count_flip_identical = 0; // count values <= n which when flipped are identical\n for (int i=0; i < s.length(); i++) {\n // These are like the above counts, but only for numbers prefixed with s[0..i]\n int count_prefix_valid_digits = 1;\n int count_prefix_flip_identical = 1;\n for (int j=0; j < s.length(); j++) {\n bool before_middle = (j < s.length()/2);\n bool middle_pos = (s.length() % 2 == 1 && j == s.length()/2);\n bool after_middle = (j >= s.length()/2);\n\n if (j < i) {\n // Must be equal to this specific value\n if (!is_flippable(s[j])) {\n count_prefix_valid_digits = 0;\n count_prefix_flip_identical = 0;\n break;\n } else if (middle_pos && !is_flippable_no_change(s[j])) {\n count_prefix_flip_identical = 0;\n } else if (after_middle && flipped(s[s.length() - 1 - j]) != s[j]) {\n count_prefix_flip_identical = 0;\n }\n } else if (j == i) {\n // Must be less than this specific value (or <= in last position)\n int count_less = less_flippable(s[j], j == 0, j == s.length() - 1);\n count_prefix_valid_digits *= count_less;\n\n if (before_middle) {\n count_prefix_flip_identical *= count_less;\n } else if (middle_pos) {\n count_prefix_flip_identical *= \n less_flippable_no_change(s[j], j == 0, j == s.length() - 1);\n } else if (after_middle) {\n if (flipped(s[s.length() - 1 - j]) >= s[j]) {\n count_prefix_flip_identical = 0; // Cannot choose matching digit\n } else {\n count_prefix_flip_identical *= 1; // Choose matching digit\n }\n }\n if (count_less == 0) break;\n } else { // j > i\n // Can be any value\n count_prefix_valid_digits *= num_flippable_digits;\n if (before_middle) {\n count_prefix_flip_identical *= num_flippable_digits;\n } else if (middle_pos) {\n count_prefix_flip_identical *= num_flippable_digits_no_change;\n } else if (after_middle) {\n count_prefix_flip_identical *= 1; // Must match corresponding digit before middle\n }\n }\n }\n\n count_with_valid_digits += count_prefix_valid_digits;\n count_flip_identical += count_prefix_flip_identical;\n }\n return count_with_valid_digits - count_flip_identical;\n }\n\n int confusingNumberII(int n) {\n int result = countConfusingNumbersOfMaxLength(n);\n int power10 = 1;\n int power10_length = 1;\n int n_length = to_string(n).length();\n while (n_length > power10_length) {\n power10 *= 10;\n power10_length++;\n result += countConfusingNumbersOfMaxLength(power10 - 1);\n }\n return result;\n }\n};\n```

Confusing Number II

Problem Description

Problem Description

Answer Panel