Posts tagged as “math”

花花酱 LeetCode 1887. Reduction Operations to Make the Array Elements Equal

By zxi on August 8, 2021

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

Example 1:

Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

Example 2:

Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

Example 3:

Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

Constraints:

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 5 * 10⁴

Solution: Math

Input: [5,4,3,2,1]
[5,4,3,2,1] -> [4,4,3,2,1] 5->4, 1 op
[4,4,3,2,1] -> [3,3,3,2,1] 4->3, 2 ops
[3,3,3,2,1] -> [2,2,2,2,1] 3->2, 3 ops
[2,2,2,2,1] -> [1,1,1,1,1] 2->1, 4 ops
total = 1 + 2 + 3 + 4 = 10

Sort the array in reverse order, if we find a number at index i that is is smaller than the previous number, we need i ops to make all the numbers before it to become itself.

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

C++

// Author: Huahua

class Solution {

public:

int reductionOperations(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

int ans = 0;

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

if (nums[i] != nums[i - 1]) ans += i;

return ans;

}

};

花花酱 LeetCode 1884. Egg Drop With 2 Eggs and N Floors

By zxi on August 8, 2021

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting
  from floor 1 and going up one at a time to find f within 7 more drops. Total drops is 1 + 7 = 8.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9
  and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more
  drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45,
  55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

Constraints:

1 <= n <= 1000

Solution: Math

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

C++

class Solution {

public:

int twoEggDrop(int n) {

int ans{0};

while (ans < n) n -= ans++;

return ans;

}

};

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

By zxi on August 6, 2021

You are given an m x n integer matrix grid.

A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Example 1:

Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 20 + 3 + 200 + 5 = 228
- Red: 200 + 2 + 10 + 4 = 216
- Green: 5 + 200 + 4 + 2 = 211

Example 2:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 4 + 2 + 6 + 8 = 20
- Red: 9 (area 0 rhombus in the bottom right corner)
- Green: 8 (area 0 rhombus in the bottom middle)

Example 3:

Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁵

Solution: Brute Force

Just find all Rhombus…

Time complexity: O(mn*min(n,m)²)
Space complexity: O(mn*min(n,m)²)

C++

// Author: Huahua

class Solution {

public:

vector<int> getBiggestThree(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> ans;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

ans.push_back(grid[i][j]);

for (int a = 2; a <= min(m, n); ++a)

for (int cy = a - 1; cy + a <= m; ++cy)

for (int cx = a - 1; cx + a <= n; ++cx) {

int s = grid[cy][cx - a + 1]

+ grid[cy][cx + a - 1]

+ grid[cy + a - 1][cx]

+ grid[cy - a + 1][cx];

for (int i = 1; i < a - 1; ++i)

s += grid[cy - i][cx - a + i + 1]

+ grid[cy - i][cx + a - i - 1]

+ grid[cy + i][cx - a + i + 1]

+ grid[cy + i][cx + a - i - 1];

ans.push_back(s);

}

sort(rbegin(ans), rend(ans));

vector<int> output;

for (int x : ans) {

if (output.empty() || output.back() != x)

output.push_back(x);

if (output.size() == 3) break;

}

return output;

}

};

花花酱 LeetCode 1837. Sum of Digits in Base K

By zxi on April 25, 2021

Given an integer n (in base 10) and a base k, return the sum of the digits of n after converting n from base 10 to base k.

After converting, each digit should be interpreted as a base 10 number, and the sum should be returned in base 10.

Example 1:

Input: n = 34, k = 6
Output: 9
Explanation: 34 (base 10) expressed in base 6 is 54. 5 + 4 = 9.

Example 2:

Input: n = 10, k = 10
Output: 1
Explanation: n is already in base 10. 1 + 0 = 1.

Constraints:

1 <= n <= 100
2 <= k <= 10

Solution: Base Conversion

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

C++

// Author: Huahua

class Solution {

public:

int sumBase(int n, int k) {

int ans = 0;

while (n) {

ans += n % k;

n /= k;

}

return ans;

}

};

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

By zxi on April 18, 2021

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".

Example 2:

Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".

Example 3:

Input: s = "cdbea"
Output: 63

Example 4:

Input: s = "leetcodeleetcodeleetcode"
Output: 982157772

Constraints:

1 <= s.length <= 3000
s consists only of lowercase English letters.

Solution: Math

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

C++

constexpr int kMod = 1e9 + 7;

int64_t powm(int64_t b, int64_t p) {

int64_t ans = 1;

while (p) {

if (p & 1) ans = (ans * b) % kMod;

b = (b * b) % kMod;

p >>= 1;

}

return ans;

}

class Solution {

public:

int makeStringSorted(string s) {

const int n = s.length();

vector<int64_t> fact(n + 1, 1);

vector<int64_t> inv(n + 1, 1);

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

fact[i] = (fact[i - 1] * i) % kMod;

inv[i] = powm(fact[i], kMod - 2);

}

int64_t ans = 0;

vector<int> freq(26);

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

const int idx = s[i] - 'a';

++freq[idx];

int64_t cur = accumulate(begin(freq), begin(freq) + idx, 0ll) *

fact[n - i - 1] % kMod;

for (int f : freq)

cur = cur * inv[f] % kMod;

ans = (ans + cur) % kMod;

}

return ans;

}

};