Posts published in “Math”

花花酱 LeetCode 453. Minimum Moves to Equal Array Elements

By zxi on April 5, 2018

Problem

题目大意：给你一个数组，每次可以把其中n-1个数加1，问最少需要多少次操作可以使得数组中的元素都相等。

https://leetcode.com/problems/minimum-moves-to-equal-array-elements/description/

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Idea

Assuming the sum of array is S, the minimum element of the array is min and minimum number of moves is m.

Each move will increase the sum of array by n – 1. Finally, every element becomes x. So we have:

S + (n – 1) * m = x * n
min + m = x

We got: m = S – n * min

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 51 ms

class Solution {

public:

int minMoves(const vector<int>& a) {

return accumulate(a.begin(), a.end(), 0L) - a.size() * *min_element(a.begin(), a.end());

}

};

Python

"""

Author: Huahua

Running time: 104 ms

"""

class Solution:

def minMoves(self, nums):

return sum(nums) - len(nums) * min(nums)

花花酱 LeetCode 507. Perfect Number

By zxi on March 22, 2018

Problem

题目大意：判断一个数的因数和是不是等于它本身。

https://leetcode.com/problems/perfect-number/description/

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

Solution: Brute Force

Try allnumbers from 1 to n – 1.

Time complexity: O(n) TLE for prime numbers

Space complexity: O(1)

Solution: Math

Try all numbers from 2 to sqrt(n).

If number i is a divisor of n then n/i is another one.

Be careful about the case when i == n/i, only one should be added to the sum.

Time complexity: O(sqrt(n))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkPerfectNumber(int num) {

if (num <= 1) return false;

int sum = 1;

for (int i = 2; i <= sqrt(num); ++i)

if (num % i == 0) sum += i + ((i == num / i) ? 0 : num / i);

return sum == num;

}

};

花花酱 LeetCode 553. Optimal Division

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/optimal-division/description/

题目大意：给你一个连除的表达式，让你加一些括号使得表达式的值最大。

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
since they don't influence the operation priority. So you should return "1000/(100/10/2)". 

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

Solution: Math

For: X1/X2/X3/…/Xn, X1/(X2/X3/…/Xn) > X1/X2/(X3/…/Xn) > X1/X2/X3/(…/Xn)

X1/(X2/X3/…/Xn) is the max value.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

string optimalDivision(vector<int>& nums) {

string ans = to_string(nums[0]);

if (nums.size() == 1) return ans;

else if (nums.size() == 2) return ans + "/" + to_string(nums[1]);

ans += "/(" + to_string(nums[1]);

for (int i = 2; i < nums.size(); ++i)

ans += "/" + to_string(nums[i]);

ans += ")";

return ans;

}

};

花花酱 LeetCode 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

for (int i = 0; i < n; ++i) {

sum += A[i];

f += i * A[i];

}

int ans = f;

for (int i = 0; i < n - 1; ++i) {

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

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

Posts published in “Math”

花花酱 LeetCode 453. Minimum Moves to Equal Array Elements

Problem

Idea

Solution: Math

花花酱 LeetCode 507. Perfect Number

Problem

Solution: Brute Force

Solution: Math

花花酱 LeetCode 553. Optimal Division

Problem

Example:

Note:

Solution: Math

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math

花花酱 LeetCode 172. Factorial Trailing Zeroes

Problem:

Idea:

Solution 1: Recursion

C++

Java

Python3

Related Problems: