Posts published in “Math”

花花酱 LeetCode 1952. Three Divisors

By zxi on December 31, 2021

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

Constraints:

1 <= n <= 10⁴

Solution: Enumerate divisors.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

for (int i = 1; i <= n; ++i)

if (n % i == 0) ++c;

return c == 3;

}

};

Optimization

Only need to enumerate divisors up to sqrt(n). Special handle for the d * d == n case.

Time complexity: O(sqrt(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

for (int i = 1; i <= sqrt(n); ++i)

if (n % i == 0)

c += 1 + (i * i != n);

return c == 3;

}

};

花花酱 LeetCode 1936. Add Minimum Number of Rungs

By zxi on December 31, 2021

You are given a strictly increasing integer array rungs that represents the height of rungs on a ladder. You are currently on the floor at height 0, and you want to reach the last rung.

You are also given an integer dist. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist. You are able to insert rungs at any positive integer height if a rung is not already there.

Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.

Example 1:

Input: rungs = [1,3,5,10], dist = 2
Output: 2
Explanation:
You currently cannot reach the last rung.
Add rungs at heights 7 and 8 to climb this ladder. 
The ladder will now have rungs at [1,3,5,7,8,10].

Example 2:

Input: rungs = [3,6,8,10], dist = 3
Output: 0
Explanation:
This ladder can be climbed without adding additional rungs.

Example 3:

Input: rungs = [3,4,6,7], dist = 2
Output: 1
Explanation:
You currently cannot reach the first rung from the ground.
Add a rung at height 1 to climb this ladder.
The ladder will now have rungs at [1,3,4,6,7].

Constraints:

1 <= rungs.length <= 10⁵
1 <= rungs[i] <= 10⁹
1 <= dist <= 10⁹
rungs is strictly increasing.

Solution: Math

Check two consecutive rungs, if their diff is > dist, we need insert (diff – 1) / dist rungs in between.
ex1 5 -> 11, diff = 6, dist = 2, (diff – 1) / dist = (6 – 1) / 2 = 2. => 5, 7, 9, 11.
ex2 0 -> 3, diff = 3, dist = 1, (diff – 1) / dist = (3 – 1) / 1 = 2 => 0, 1, 2, 3

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int addRungs(vector<int>& rungs, int dist) {

int ans = 0;

for (size_t i = 0; i < rungs.size(); ++i)

ans += (rungs[i] - (i ? rungs[i - 1] : 0) - 1) / dist;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def addRungs(self, rungs: List[int], dist: int) -> int:

return sum((r - 1 - (rungs[i - 1] if i else 0)) // dist for i, r in enumerate(rungs))

花花酱 LeetCode 1925. Count Square Sum Triples

By zxi on December 30, 2021

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

Example 1:

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10
Output: 4
Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

Constraints:

1 <= n <= 250

Solution: Enumerate a & b

Brute force enumerates a & b & c, which takes O(n³). Just need to enumerate a & b and validate c.

Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countTriples(int n) {

int ans = 0;

for (int a = 1; a <= n; ++a)

for (int b = 1; b <= n; ++b) {

int c = sqrt(a * a + b * b);

if (c <= n && c * c == a * a + b * b) ++ans;

}

return ans;

}

};

花花酱 LeetCode 2117. Abbreviating the Product of a Range

By zxi on December 26, 2021

You are given two positive integers left and right with left <= right. Calculate the product of all integers in the inclusive range [left, right].

Since the product may be very large, you will abbreviate it following these steps:

Count all trailing zeros in the product and remove them. Let us denote this count as C.
- For example, there are 3 trailing zeros in 1000, and there are 0 trailing zeros in 546.
Denote the remaining number of digits in the product as d. If d > 10, then express the product as <pre>...<suf> where <pre> denotes the first 5 digits of the product, and <suf> denotes the last 5 digits of the product after removing all trailing zeros. If d <= 10, we keep it unchanged.
- For example, we express 1234567654321 as 12345...54321, but 1234567 is represented as 1234567.
Finally, represent the product as a string "<pre>...<suf>eC".
- For example, 12345678987600000 will be represented as "12345...89876e5".

Return a string denoting the abbreviated product of all integers in the inclusive range [left, right].

Example 1:

Input: left = 1, right = 4
Output: "24e0"
Explanation:
The product is 1 × 2 × 3 × 4 = 24.
There are no trailing zeros, so 24 remains the same. The abbreviation will end with "e0".
Since the number of digits is 2, which is less than 10, we do not have to abbreviate it further.
Thus, the final representation is "24e0".

Example 2:

Input: left = 2, right = 11
Output: "399168e2"
Explanation:
The product is 39916800.
There are 2 trailing zeros, which we remove to get 399168. The abbreviation will end with "e2".
The number of digits after removing the trailing zeros is 6, so we do not abbreviate it further.
Hence, the abbreviated product is "399168e2".

Example 3:

Input: left = 999998, right = 1000000
Output: "99999...00002e6"
Explanation:
The above diagram shows how we abbreviate the product to "99999...00002e6".
- It has 6 trailing zeros. The abbreviation will end with "e6".
- The first 5 digits are 99999.
- The last 5 digits after removing trailing zeros is 00002.

Constraints:

1 <= left <= right <= 10⁶

Solution: Prefix + Suffix

Since we only need the first 5 digits and last 5 digits, we can compute prefix and suffix separately with 15+ effective digits. Note, if using long/int64 with (18 – 6) = 12 effective digits, it may fail on certain test cases. Thus, here we use Python with 18 effective digits.

Time complexity: O(mlog(right)) where m = right – left + 1
Space complexity: O(1)

Python3

# Author: Huahua

class Solution:

def abbreviateProduct(self, left: int, right: int) -> str:

kMax = 10 ** 18

prefix = 1

suffix = 1

c = 0

for i in range(left, right + 1):

prefix *= i

while prefix >= kMax:

prefix //= 10

suffix *= i

while suffix % 10 == 0:

suffix //= 10

c += 1

suffix %= kMax

p, s = str(prefix), str(suffix)

return (s if len(s) <= 10 else p[:5] + "..." + s[-5:]) + "e" + str(c);

花花酱 LeetCode 2119. A Number After a Double Reversal

By zxi on December 26, 2021

Reversing an integer means to reverse all its digits.

For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer num, reverse num to get reversed1, then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

0 <= num <= 10⁶

Solution: Math

The number must not end with 0 expect 0 itself.

e.g. 1230 => 321 => 123
e.g. 0 => 0 => 0

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isSameAfterReversals(int num) {

return num == 0 || num % 10;

}

};