Posts published in “Math”

花花酱 LeetCode 1894. Find the Student that Will Replace the Chalk

By zxi on August 9, 2021

There are n students in a class numbered from 0 to n - 1. The teacher will give each student a problem starting with the student number 0, then the student number 1, and so on until the teacher reaches the student number n - 1. After that, the teacher will restart the process, starting with the student number 0 again.

You are given a 0-indexed integer array chalk and an integer k. There are initially k pieces of chalk. When the student number i is given a problem to solve, they will use chalk[i] pieces of chalk to solve that problem. However, if the current number of chalk pieces is strictly less than chalk[i], then the student number i will be asked to replace the chalk.

Return the index of the student that will replace the chalk.

Example 1:

Input: chalk = [5,1,5], k = 22
Output: 0
Explanation: The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.

Example 2:

Input: chalk = [3,4,1,2], k = 25
Output: 1
Explanation: The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.

Constraints:

chalk.length == n
1 <= n <= 10⁵
1 <= chalk[i] <= 10⁵
1 <= k <= 10⁹

Solution: Math

Sum up all the students. k %= sum to skip all the middle rounds.

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

C++

// Author: Huahua

class Solution {

public:

int chalkReplacer(vector<int>& chalk, int k) {

long sum = accumulate(begin(chalk), end(chalk), 0L);

k %= sum;

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

if ((k -= chalk[i]) < 0) return i;

return -1;

}

};

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

}

};