FilesExpand file tree

master

/

super-ugly-number.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

139 lines (120 loc) · 4.05 KB

master

/

super-ugly-number.py

Copy path

Top

File metadata and controls

• Code
• Blame

139 lines (120 loc) · 4.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

133

134

135

136

137

138

139

# Time: O(n * logk) ~ O(n * k)

# Space: O(n + k)

# Write a program to find the nth super ugly number.

#

# Super ugly numbers are positive numbers whose all

# prime factors are in the given prime list primes of size k.

# For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

# is the sequence of the first 12 super ugly numbers given

# primes = [2, 7, 13, 19] of size 4.

#

# Note:

# (1) 1 is a super ugly number for any given primes.

# (2) The given numbers in primes are in ascending order.

# (3) 0 < k <= 100, 0 < n <= 106, 0 < primes[i] < 1000.

# Heap solution. (620ms)

class Solution(object):

def nthSuperUglyNumber(self, n, primes):

"""

:type n: int

:type primes: List[int]

:rtype: int

"""

heap, uglies, idx, ugly_by_last_prime = [], [0] * n, [0] * len(primes), [0] * n

uglies[0] = 1

for k, p in enumerate(primes):

heapq.heappush(heap, (p, k))

for i in xrange(1, n):

uglies[i], k = heapq.heappop(heap)

ugly_by_last_prime[i] = k

idx[k] += 1

while ugly_by_last_prime[idx[k]] > k:

idx[k] += 1

heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

return uglies[-1]

# Time: O(n * k)

# Space: O(n + k)

# Hash solution. (932ms)

class Solution2(object):

def nthSuperUglyNumber(self, n, primes):

"""

:type n: int

:type primes: List[int]

:rtype: int

"""

uglies, idx, heap, ugly_set = [0] * n, [0] * len(primes), [], set([1])

uglies[0] = 1

for k, p in enumerate(primes):

heapq.heappush(heap, (p, k))

ugly_set.add(p)

for i in xrange(1, n):

uglies[i], k = heapq.heappop(heap)

while (primes[k] * uglies[idx[k]]) in ugly_set:

idx[k] += 1

heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

ugly_set.add(primes[k] * uglies[idx[k]])

return uglies[-1]

# Time: O(n * logk) ~ O(n * klogk)

# Space: O(n + k)

class Solution3(object):

def nthSuperUglyNumber(self, n, primes):

"""

:type n: int

:type primes: List[int]

:rtype: int

"""

uglies, idx, heap = [1], [0] * len(primes), []

for k, p in enumerate(primes):

heapq.heappush(heap, (p, k))

for i in xrange(1, n):

min_val, k = heap[0]

uglies += [min_val]

while heap[0][0] == min_val: # worst time: O(klogk)

min_val, k = heapq.heappop(heap)

idx[k] += 1

heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

return uglies[-1]

# Time: O(n * k)

# Space: O(n + k)

# TLE due to the last test case, but it passess and performs the best in C++.

class Solution4(object):

def nthSuperUglyNumber(self, n, primes):

"""

:type n: int

:type primes: List[int]

:rtype: int

"""

uglies = [0] * n

uglies[0] = 1

ugly_by_prime = list(primes)

idx = [0] * len(primes)

for i in xrange(1, n):

uglies[i] = min(ugly_by_prime)

for k in xrange(len(primes)):

if uglies[i] == ugly_by_prime[k]:

idx[k] += 1

ugly_by_prime[k] = primes[k] * uglies[idx[k]]

return uglies[-1]

# Time: O(n * logk) ~ O(n * klogk)

# Space: O(k^2)

# TLE due to the last test case, but it passess and performs well in C++.

class Solution5(object):

def nthSuperUglyNumber(self, n, primes):

"""

:type n: int

:type primes: List[int]

:rtype: int

"""

ugly_number = 0

heap = []

heapq.heappush(heap, 1)

for p in primes:

heapq.heappush(heap, p)

for _ in xrange(n):

ugly_number = heapq.heappop(heap)

for i in xrange(len(primes)):

if ugly_number % primes[i] == 0:

for j in xrange(i + 1):

heapq.heappush(heap, ugly_number * primes[j])

break

return ugly_number