Posts tagged as “math”

花花酱 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 2122. Recover the Original Array

By zxi on December 26, 2021

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

lower[i] = arr[i] - k, for every index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints:

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
The test cases are generated such that there exists at least one valid array arr.

Solution: Try all possible k

Sort the array, we know that the smallest number nums[0] is org[0] – k, org[0] + k (nums[0] + 2k) must exist in nums. We try all possible ks. k = (nums[i] – nums[0]) / 2.

Then we iterate the sorted nums array as low, and see whether we can find low + 2k as high using a dynamic hashtable.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> recoverArray(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

unordered_map<int, int> m;

for (int x : nums) ++m[x];

auto check = [&](int k) -> vector<int> {

vector<int> ans;

unordered_map<int, int> cur(m);

for (int x : nums) {

if (cur[x] == 0) continue;

--cur[x];

if (--cur[x + 2 * k] < 0) return {};

ans.push_back(x + k);

}

return ans;

};

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

if (nums[i] == nums[0] || (nums[i] - nums[0]) & 1) continue;

const int k = (nums[i] - nums[0]) / 2;

vector<int> ans = check(k);

if (!ans.empty()) return ans;

}

return {};

}

};

花花酱 LeetCode 2121. Intervals Between Identical Elements

By zxi on December 26, 2021

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length
1 <= n <= 10⁵
1 <= arr[i] <= 10⁵

Solution: Math / Hashtable + Prefix Sum

For each arr[i], suppose it occurs in the array of total c times, among which k of them are in front of it and c – k – 1 of them are after it. Then the total sum intervals:
(i – j₁) + (i – j₂) + … + (i – j_k) + (j_k+1-i) + (j_k+2-i) + … + (j_c-i)
<=> k * i – sum(j₁~j_k) + sum(j_k+1~j_c) – (c – k – 1) * i

Use a hashtable to store the indies of each unique number in the array and compute the prefix sum for fast range sum query.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> getDistances(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<long long>> m;

vector<int> pos(n);

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

m[arr[i]].push_back(i);

pos[i] = m[arr[i]].size() - 1;

}

for (auto& [k, idx] : m)

partial_sum(begin(idx), end(idx), begin(idx));

vector<long long> ans(n);

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

const auto& sums = m[arr[i]];

const long long k = pos[i];

const long long c = sums.size();

if (k > 0) ans[i] += k * i - sums[k - 1];

if (k + 1 < c) ans[i] += (sums[c - 1] - sums[k]) - (c - k - 1) * i;

}

return ans;

}

};