Given two integers num and k, return the largest product of k contiguous digits in num.
Note: num is guaranteed to have >= k digits.
Example 1
Input
num = 41598671
k = 3
Output
432
Explanation
The largest product of 3 contiguous digits is 9 * 8 * 6 = 432.Example 2
Input
num = 77510373
k = 6
Output
0
Explanation
The digits have to be contiguous and 0 appears in every k-sized window, so we must return 0.
O(NK) Bruteforce Algorithm to Compute the Largest Product
The bruteforce algorithm is intuitive. We check every K-size window and comptue the product of such.
This runs at O(NK) time.
1 2 3 4 5 6 7 8 9 10 | class Solution: def largestProductOfContinuousDigits(self, num, k): s = str(num) ans = 0 for i in range(len(s) - k + 1): cur = 1 for j in range(k): cur *= int(s[i + j]) ans = max(ans, cur) return ans |
class Solution:
def largestProductOfContinuousDigits(self, num, k):
s = str(num)
ans = 0
for i in range(len(s) - k + 1):
cur = 1
for j in range(k):
cur *= int(s[i + j])
ans = max(ans, cur)
return ansO(N) Sliding Window Algorithm to Compute the Largest Product of Continuous Digits
We can also separate the number by zeros, and skip those segments with size smaller than K as their product will be zero no matter what.
Then, we can compute the product for other segments.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: def largestProductOfContinuousDigits(self, num, k): arr = str(num).split('0') ans = 0 for i in arr: if len(i) < k: continue cur = 1 for j in range(len(i)): cur *= int(i[j]) if j >= k: cur //= int(i[j - k]) if j >= k - 1: ans = max(cur, ans) return ans |
class Solution:
def largestProductOfContinuousDigits(self, num, k):
arr = str(num).split('0')
ans = 0
for i in arr:
if len(i) < k:
continue
cur = 1
for j in range(len(i)):
cur *= int(i[j])
if j >= k:
cur //= int(i[j - k])
if j >= k - 1:
ans = max(cur, ans)
return ansAs each segment does not contain zeros, thus we can use the sliding window algorithm to dynamically update the product for K-size window.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution: def largestProductOfContinuousDigits(self, num, k): s = str(num) ans = 0 arr = str(num).split('0') for a in arr: if len(a) < k: continue cur = 1 for i in range(k): cur *= int(a[i]) ans = max(ans, cur) # sliding window i, j = 0, k while j < len(a): cur *= int(a[j]) cur //= int(a[i]) ans = max(ans, cur) i += 1 j += 1 return ans |
class Solution:
def largestProductOfContinuousDigits(self, num, k):
s = str(num)
ans = 0
arr = str(num).split('0')
for a in arr:
if len(a) < k:
continue
cur = 1
for i in range(k):
cur *= int(a[i])
ans = max(ans, cur)
# sliding window
i, j = 0, k
while j < len(a):
cur *= int(a[j])
cur //= int(a[i])
ans = max(ans, cur)
i += 1
j += 1
return ansThe runtime complexity on average is reduced to O(N).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Simple Vertical Cipher Algorithm
Next Post: Teaching Kids Programming - Algorithmic Runtime and Space Complexity
