1088. Confusing Number II.js

// We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.
// A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)
// Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.
//
// Example 1:
//
// Input: 20
// Output: 6
// Explanation:
// The confusing numbers are [6,9,10,16,18,19].
// 6 converts to 9.
// 9 converts to 6.
// 10 converts to 01 which is just 1.
// 16 converts to 91.
// 18 converts to 81.
// 19 converts to 61.
//
// Example 2:
//
// Input: 100
// Output: 19
// Explanation:
// The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
//
// Note:
//
// 1 <= N <= 10^9

/**
 * @param {number} N
 * @return {number}
 */

// Backtracking
const confusingNumberII = (N) => {
  const nums = [0, 1, 6, 8, 9];
  let res = 0;

  const go = (n) => {
    if (n > N) return;
    if (n <= N && !isRotateEqual(n)) res++;

    const start = n === 0 ? 1 : 0;
    for (let i = start; i < nums.length; i++) {
      go(n * 10 + nums[i]);
    }
  };

  go(0);
  return res;
};

const isRotateEqual = (n) => {
  const map = {
    0: 0,
    1: 1,
    8: 8,
    6: 9,
    9: 6,
  };
  let s = '';
  for (const c of String(n)) {
    s = String(map[c]) + s;
  }
  return n === Number(s);
};