Press "Enter" to skip to content

Posts tagged as “math”

花花酱 LeetCode 172. Factorial Trailing Zeroes

题目大意:求n!末尾0的个数。

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))

C++

Java

Python3

Related Problems:

花花酱 LeetCode 789. Escape The Ghosts

题目大意:给你目的地坐标以及幽灵的坐标,初始点在(0,0),每次你和幽灵都可以移动一步。问你是否可以安全到达终点。

You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target[1]). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghosts[i][1]).

Each turn, you and all ghosts simultaneously *may* move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.)  If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.

Return True if and only if it is possible to escape.

Note:

  • All points have coordinates with absolute value <= 10000.
  • The number of ghosts will not exceed 100.

Solution: Greedy / Math

You can escape if and only if no ghosts can reach target before you. Just need to compare the Manhattan distance.

如果所有的幽灵都无法在你之前到达target,那么你可以逃脱。只要比较曼哈顿距离即可。

C++

Time complexity: O(|ghost|)

Java

Python3

 

花花酱 LeetCode. 69 Sqrt(x)

题目大意:让你实现开根号函数,只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

 

 

Solution 1: Brute force

Time complexity: sqrt(x)

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

Time complexity: O(logn)

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 754. Reach a Number

题目大意:第i时刻可以移动+i,-i单位距离。初始在原点,问最少对少时间可以移动到target坐标。

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Example 2:

Note:

  • target will be a non-zero integer in the range [-10^9, 10^9].

 


Idea:

Math

 

Time complexity: O(sqrt(target))

Space complexity: O(1)

O(1)

 

花花酱 LeetCode 204. Count Primes

Problem:

Count the number of prime numbers less than a non-negative number, n.

Idea:

Sieve of Eratosthenes

Time Complexity:

O(nloglogn)

Space Complexity:

O(n)

Solution:

C++

Java

Python3