Problem:

https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

Solution 1: Recursion

Time complexity: O(log5(n))

Space complexity: O(log5(n))

Related Problems:

Problem:

https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Example 2:

Note:

• s.length will be between 1 and 50,000.
• s will only consist of “0” or “1” characters.

Solution 0: Search

Try all possible substrings and check whether it’s a valid one or not.

Time complexity O(2^n * n) TLE

Space complexity: O(n)

Solution 1: Running Length

For S = “000110”, there are two virtual blocks “[00011]0” and “000[110]” which contains consecutive 0s and 1s or (1s and 0s)

Keep tracking of the running length of 0, 1 for each block

“00011” => ‘0’: 3, ‘1’:2

ans += min(3, 2) => ans = 2 (“[0011]”, “0[01]1”)

“110” => ‘0’: 1, ‘1’: 2

ans += min(1, 2) => ans = 3 (“[0011]”, “0[01]1”, “1[10]”)

We can reuse part of the running length from last block.

Time complexity: O(n)

Space complexity: O(1)

C++

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1 and the result is guaranteed to be at most 231 – 1.

Example:

Solution 1: HashTable

Split the arrays into two groups: (A, B), (C, D)

Create the Minkowski sum of two groups and count the occurrence of each element.

e.g. A = [1, 2, 3], B = [0, -1, 1]

Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]

for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD

ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

Python3

Related Problems:

You need to find the largest value in each row of a binary tree.

Example:

Solution 1: Inorder traversal + depth info

C++

Python3

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Example 2:

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

Python3

Mission News Theme by Compete Themes.