Compute Largest Product of Contiguous Digits

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.

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

O(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.

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

As each segment does not contain zeros, thus we can use the sliding window algorithm to dynamically update the product for K-size window.

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

The runtime complexity on average is reduced to O(N).

–EOF (The Ultimate Computing & Technology Blog) —