forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathconfusing-number-ii.py
132 lines (122 loc) · 5.46 KB
/
confusing-number-ii.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
# Time: O(logn)
# Space: O(logn)
class Solution(object):
def confusingNumberII(self, n):
"""
:type n: int
:rtype: int
"""
lookup = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
centers = {"0":"0", "1":"1", "8":"8"}
def totalCount(n): # count all numbers in the pattern of [01689]{1,len(n)} in the range of [1, n]
s = str(n)
total = 0
p = len(lookup)**(len(s)-1)
for i in xrange(len(s)+1):
if i == len(s):
total += 1
break
smaller = sum(int(c < s[i]) for c in lookup.iterkeys())
total += smaller * p
if s[i] not in lookup:
break
p //= len(lookup)
return total-1 # exclude 0
def validCountInLessLength(n): # count unconfusing numbers in the pattern of [01689]{1,len(n)-1} in the range of [1, n]
s = str(n)
valid = 0
total = len(centers)
for i in xrange(1, len(s), 2): # count unconfusing numbers for each odd length less than s
if i == 1:
valid += len({c for c in centers.iterkeys() if c != '0'})
else:
valid += total * (len(lookup)-1)
total *= len(lookup)
total = 1
for i in xrange(2, len(s), 2): # count unconfusing numbers for each even length less than s
valid += total * (len(lookup)-1)
total *= len(lookup)
return valid
def validCountInFullLength(n): # count unconfusing numbers in the pattern of [01689]{len(n)} in the range of [1, n]
s = str(n)
half_s = s[:(len(s)+1)//2]
total = 0
choices = centers if (len(s) % 2) else lookup
p = int(len(lookup)**(len(half_s)-2) * len(choices))
for i in xrange(len(half_s)):
if i == len(half_s)-1:
total += sum(int(c < half_s[i]) for c in choices.iterkeys() if i != 0 or c != '0')
if half_s[i] not in choices:
break
tmp = list(half_s)+[lookup[half_s[i]] for i in reversed(xrange(len(half_s)-(len(s) % 2)))]
total += 0 < int("".join(tmp)) <= n
break
smaller = sum(int(c < half_s[i]) for c in lookup.iterkeys() if i != 0 or c != '0')
total += smaller * p
if half_s[i] not in lookup:
break
p //= len(lookup)
return total
return totalCount(n) - validCountInLessLength(n) - validCountInFullLength(n)
# Time: O(logn)
# Space: O(logn)
class Solution2(object):
def confusingNumberII(self, n):
"""
:type n: int
:rtype: int
"""
lookup = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
centers = {"0":"0", "1":"1", "8":"8"}
def totalCount(n): # count all numbers in the pattern of [01689]{1,len(n)} in the range of [0, n]
s = str(n)
total = 0
p = len(lookup)**(len(s)-1)
for i in xrange(len(s)+1):
if i == len(s):
total += 1
break
smaller = sum(int(c < s[i]) for c in lookup.iterkeys())
total += smaller * p
if s[i] not in lookup:
break
p //= len(lookup)
return total
def validCountInLessLength(n): # count unconfusing numbers in the pattern of [01689]{1,len(n)-1} in the range of [0, n]
s = str(n)
valid = 0
total = len(centers)
for i in xrange(1, len(s), 2): # count unconfusing numbers for each odd length less than s
if i == 1:
valid += len(centers)
else:
valid += total * (len(lookup)-1)
total *= len(lookup)
total = 1
for i in xrange(2, len(s), 2): # count unconfusing numbers for each even length less than s
valid += total * (len(lookup)-1)
total *= len(lookup)
return valid
def validCountInFullLength(n): # count unconfusing numbers in the pattern of [01689]{len(n)} in the range of [0, n]
s = str(n)
half_s = s[:(len(s)+1)//2]
total = 0
choices = centers if (len(s) % 2) else lookup
p = int(len(lookup)**(len(half_s)-2) * len(choices))
for i in xrange(len(half_s)):
if i == len(half_s)-1:
total += sum(int(c < half_s[i]) for c in choices.iterkeys() if len(s) != 2 or c != '0')
if half_s[i] not in choices:
break
tmp = list(half_s)+[lookup[half_s[i]] for i in reversed(xrange(len(half_s)-(len(s) % 2)))]
total += int("".join(tmp)) <= n
break
smaller = sum(int(c < half_s[i]) for c in lookup.iterkeys() if i != 0 or c != '0')
total += smaller * p
if half_s[i] not in lookup:
break
p //= len(lookup)
return total
def f(n): # count confusing numbers in the range of [0, n]
return totalCount(n) - validCountInLessLength(n) - validCountInFullLength(n)
return f(n) - f(0) # f(0) is always 0 and could be ignored