Posts published in “Math”

花花酱 LeetCode 172. Factorial Trailing Zeroes

By zxi on March 6, 2018

题目大意：求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++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

public int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

Python3

"""

Author: Huahua

Running time: 68 ms

"""

class Solution:

def trailingZeroes(self, n):

return 0 if n < 5 else n // 5 + self.trailingZeroes(n // 5)

Related Problems:

花花酱 LeetCode 793. Preimage Size of Factorial Zeroes Function

花花酱 LeetCode 793. Preimage Size of Factorial Zeroes Function

By zxi on March 4, 2018

Let f(x) be the number of zeroes at the end of x!. (Recall that x! = 1 * 2 * 3 * ... * x, and by convention, 0! = 1.)

For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.

Example 1:

Input: K = 0

Output: 5

Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.

Example 2:

Input: K = 5

Output: 0

Explanation: There is no x such that x! ends in K = 5 zeroes.

Note:

K will be an integer in the range [0, 10^9].

Idea:

First we need to compute how many trailing zeros n! has.

See 花花酱 LeetCode 172. Factorial Trailing Zeroes for details

It’s hard to say how many numbers have trailing zeros equals to K, but we can find the largest number p whose trailing zeros is K using binary search. (p+1)! has more than K trailing zeros. And do the same thing to find the largest number q whose trailing zeros is K – 1 using binary search.

Then we know that are exact p numbers 1,2,…,p whose trailing zeros are less or equal to K.

And exact q numbers 1, 2, …, q whose trailing zeros are less or equal to K – 1.

q + 1, q + 2, …, m (m – q numbers in total) the numbers with trailing zeros equal to K.

Solution 1: Math + Binary Search

Time complexity: O(log2(INT_MAX)*log5(INT_MAX))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int preimageSizeFZF(int K) {

return g(K) - g(K - 1);

}

private:

// Find the largest number l, that numZeros(l!) == K and numZeros((l+1)!) > K

int g(int K) {

int l = 0;

int r = INT_MAX;

while (l < r) {

int m = l + (r - l) / 2;

int zeros = numZeros(m);

if (zeros <= K)

l = m + 1;

else

r = m;

}

return l;

}

int numZeros(int n) {

return n < 5 ? 0 : n / 5 + numZeros(n / 5);

}

};

花花酱 LeetCode 789. Escape The Ghosts

By zxi on February 24, 2018

题目大意：给你目的地坐标以及幽灵的坐标，初始点在(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.

Example 1:

Input:

ghosts = [[1, 0], [0, 3]]

target = [0, 1]

Output: true

Explanation:

You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.

Example 2:

Input:

ghosts = [[1, 0]]

target = [2, 0]

Output: false

Explanation:

You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:

Input:

ghosts = [[2, 0]]

target = [1, 0]

Output: false

Explanation:

The ghost can reach the target at the same time as you.

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

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {

const int steps = abs(target[0]) + abs(target[1]);

for (const auto& g: ghosts)

if (abs(g[0] - target[0]) + abs(g[1] - target[1]) <= steps)

return false;

return true;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public boolean escapeGhosts(int[][] ghosts, int[] target) {

final int steps = Math.abs(target[0]) + Math.abs(target[1]);

for (int[] g : ghosts)

if (Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]) <= steps)

return false;

return true;

}

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def escapeGhosts(self, ghosts, target):

steps = abs(target[0]) + abs(target[1])

return not any(abs(x - target[0]) + abs(y - target[1]) <= steps for x, y in ghosts)

花花酱 LeetCode. 69 Sqrt(x)

By zxi on January 16, 2018

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

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:

1 2	Input: 4 Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842...

Solution 1: Brute force

Time complexity: sqrt(x)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (long long s = 1; s <= x; ++s)

if (s * s > x) return s - 1;

return -1;

}

};

C++ div

// Author: Huahua

// Running time: 162 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (int s = 1; s <= x; ++s)

if (s > x / s) return s - 1;

return -1;

}

};

Java

// Author: Huahua

// Running time: 71 ms

class Solution {

public int mySqrt(int x) {

if (x <= 1) return x;

for (long s = 1; s <= x; ++s)

if (s * s > x) return (int)s - 1;

return -1;

}

Python3 TLE

"""

Author: Huahua

TLE: 602 / 1017 test cases passed.

"""

class Solution:

def mySqrt(self, x):

if x <= 1: return x

s = 1

while True:

if s*s > x: return s - 1

s += 1

return -1

Solution 2: Binary search

Time complexity: O(logn)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int mySqrt(int x) {

long l = 1;

long r = static_cast<long>(x) + 1;

while (l < r) {

long m = l + (r - l) / 2;

if (m * m > x) {

r = m;

} else {

l = m + 1;

}

// l: smallest number such that l * l > x

return l - 1;

}

};

Java

// Author: Huahua

// Running time: 47 ms

class Solution {

public int mySqrt(int x) {

int l = 1;

int r = x;

while (l <= r) {

int m = l + (r - l) / 2;

if (m > x / m) {

r = m - 1;

} else {

l = m + 1;

}

return r;

}

Python3

"""

Author: Huahua

Running time: 119 ms

"""

class Solution:

def mySqrt(self, a):

l = 1

r = a

while l <= r:

m = l + (r - l) // 2

if m * m > a:

r = m - 1

else:

l = m + 1

return r;

Solution 3: Newton’s method

C++ / float

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int mySqrt(int a) {

constexpr double epsilon = 1e-2;

double x = a;

while (x * x - a > epsilon) {

x = (x + a / x) / 2.0;

}

return x;

}

};

C++ / int

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

int mySqrt(int a) {

// f(x) = x^2 - a, find root of f(x)

// Newton's method

// f'(x) = 2x

// x' = x - f(x) / f'(x) = x - (1/2*x - a/(2*x))

// = (x + a / x) / 2

int x = a;

while (x > a / x)

x = (x + a / x) / 2;

return x;

}

};

Java

// Author: Huahua

// Running time: 44 ms

class Solution {

public int mySqrt(int a) {

long x = a;

while (x * x > a)

x = (x + a / x) / 2;

return (int)x;

}

Python3

"""

Author: Huahua

Running time: 100 ms

"""

class Solution:

def mySqrt(self, a):

x = a

while x * x > a:

x = (x + a // x) // 2

return x

花花酱 LeetCode 264. Ugly Number II

By zxi on January 7, 2018

题目大意：让你找到第n个丑数。

Problem:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

Solution:

C++ / O(n)

// Author: huahua

// Running time: 6 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums{1};

static int i2 = 0;

static int i3 = 0;

static int i5 = 0;

while (nums.size() < n) {

const int next2 = nums[i2] * 2;

const int next3 = nums[i3] * 3;

const int next5 = nums[i5] * 5;

const int next = min(next2, min(next3, next5));

if (next == next2) ++i2;

if (next == next3) ++i3;

if (next == next5) ++i5;

nums.push_back(next);

}

return nums[n - 1];

}

};

C++ /query * O(NlogN)

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int nthUglyNumber(int n) {

vector<int> nums;

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

return nums[n - 1];

}

};

C++ / static variables O(NlogN) + query*O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int nthUglyNumber(int n) {

static vector<int> nums;

if (nums.empty()) {

for (long a = 1; a <= INT_MAX; a *= 2)

for (long b = a; b <= INT_MAX; b *= 3)

for (long c = b; c <= INT_MAX; c *= 5)

nums.push_back(c);

std::sort(nums.begin(), nums.end());

}

return nums[n - 1];

}

};

C++ / table O(1)
leetcode_264_table.cc