Confusing number ii

Math Backtracking

47.2% acceptance

Mar 31, 2026

496

144

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid. We can rotate digits of a number by 180 degrees to form new digits. When 0, 1, 6, 8, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively. When 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid. Note that after rotating a number, we can ignore leading zeros. For example, after rotating 8000, we have 0008 which is considered as just 8. Given an integer n, return the number of confusing numbers in the inclusive range [1, n].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn confusing_number_ii(n: i32) -> i32 {
    let valid: [i64; 5] = [0, 1, 6, 8, 9];
    let rotate: [i64; 10] = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
    let mut count = 0;
    Self::dfs(0, 0, 1, &valid, &rotate, n as i64, &mut count);
    count
  }

  fn dfs(num: i64, rotated: i64, mult: i64, valid: &[i64; 5], rotate: &[i64; 10], n: i64, count: &mut i32) {
    if num > n { return; }
    if num != 0 && num != rotated { *count += 1; }
    for &d in valid {
      let new_num = num * 10 + d;
      if new_num == 0 { continue; }
      if new_num > n { break; }
      let new_rotated = rotate[d as usize] * mult + rotated;
      Self::dfs(new_num, new_rotated, mult * 10, valid, rotate, n, count);
    }
  }
}