kamyu104/LeetCode-Solutions

How to explain totalCount, validCountInLessLength, validCountInFullLength in confusing-number-ii.py?

yezhengli-Mr9 opened this issue · 3 comments

yezhengli-Mr9 commented

How to explain totalCount, validCountInLessLength, validCountInFullLength in confusing-number-ii.py?

kamyu104 commented
  • totalCount : count of all numbers in the pattern of [01689]{1,len(str(n))} in the range of [1, n]
  • validCountInLessLength : count of valid / inconfusing numbers in the pattern of [01689]{1,len(str(n))-1} in the range of [1, n]
  • validCountInFullLength : count of valid / inconfusing numbers in the pattern of [01689]{len(str(n))} in the range of [1, n]
  • Take n = 20 as an example:
    • totalCount : len([1, 6, 8, 9, 10, 11, 16, 18, 19]) = 9
    • validCountInLessLength : len([1, 8]) = 2
    • validCountInFullLength : len([11]) = 1
    • The answer is (totalCount - validCountInLessLength - validCountInFullLength) = 9 - 2 - 1 = 6
  • 👍1
yezhengli-Mr9 commented

  • totalCount : count of all numbers in the pattern of [01689]{1,len(str(n))} in the range of [1, n]

  • validCountInLessLength : count of valid / inconfusing numbers in the pattern of [01689]{1,len(str(n))-1} in the range of [1, n]

  • validCountInFullLength : count of valid / inconfusing numbers in the pattern of [01689]{len(str(n))} in the range of [1, n]

  • Take n = 20 as an example:

    • totalCount : len([1, 6, 8, 9, 10, 11, 16, 18, 19]) = 9
    • validCountInLessLength : len([1, 8]) = 2
    • validCountInFullLength : len([11]) = 1
    • The answer is (totalCount - validCountInLessLength - validCountInFullLength) = 9 - 2 - 1 = 6

Any reference for explaining validCountInFullLength(...)? Your explanation makes sense except for trivial correction (of '0' should appear in both totalCount(...) and validCountInLessLengthv):

N 20 totalCountN 10 validCountInLessLengthN 3 validCountInFullLengthN 0
N 100 totalCountN 26 validCountInLessLengthN 7 validCountInFullLengthN 0
N 95 totalCountN 22 validCountInLessLengthN 3 validCountInFullLengthN 0
N 150 totalCountN 35 validCountInLessLengthN 7 validCountInFullLengthN 1
N 195 totalCountN 47 validCountInLessLengthN 7 validCountInFullLengthN 2
N 200 totalCountN 50 validCountInLessLengthN 7 validCountInFullLengthN 3
kamyu104 commented
  • Take validCountInFullLength(98890) as an example:
    • We enumerate all valid patterns by prefix of different length the same as 98890 as follows:
      • 1YXY'1, 6YXY'9, 8YXY'8, which have prefix of length 0 the same as 98890 and are less than 98890
        • Y is the 180-degree-rotated Y', Y could be one of [0, 1, 6, 8, 9], total 5 choices
        • X could be one of [0, 1, 8], total 3 choices
        • The count of numbers in these patterns is 3 * 5 * 3 = 45
      • 90X06, 91X16, 96X96, which have prefix of length 1 the same as 98890 and are less than 98890
        • X could be one of [0, 1, 8], total 3 choices
        • The count of numbers in these patterns is 3 * 3 = 9
      • 98X86, which has prefix of length 2 the same as 98890 and is less than 98890
        • X could be one of [0, 1], total 2 choices
        • The count of numbers in this pattern is 2
      • 98886, which has prefix of length 3 same with 98890 and is less than or equal to98890
        • The count of numbers in this pattern is 1
      • The total count of validCountInFullLength(98890) is 45 + 9 + 2 + 1 = 57
  • The range of numbers in this problem is [1, n], so 0 should not be counted in all 3 functions
    • But if you want to count it, you just need to do some modifications (see Solution2 of confusing-number-ii.py)