Huahua’s Tech Road

花花酱 LeetCode 1838. Frequency of the Most Frequent Element

By zxi on April 25, 2021

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

Input: nums = [3,9,6], k = 2
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= 10⁵

Solution: Sliding Window

Sort the elements, maintain a window such that it takes at most k ops to make the all the elements equal to nums[i].

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

C++

class Solution {

public:

int maxFrequency(vector<int>& nums, int k) {

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

int l = 0;

long sum = 0;

int ans = 0;

for (int r = 0; r < nums.size(); ++r) {

sum += nums[r];

while (l < r &&

sum + k < static_cast<long>(nums[r]) * (r - l + 1))

sum -= nums[l++];

ans = max(ans, r - l + 1);

}

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 1835. Find XOR Sum of All Pairs Bitwise AND

By zxi on April 18, 2021

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Example 1:

Input: arr1 = [1,2,3], arr2 = [6,5]
Output: 0
Explanation: The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1].
The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.

Example 2:

Input: arr1 = [12], arr2 = [4]
Output: 4
Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.

Constraints:

1 <= arr1.length, arr2.length <= 10⁵
0 <= arr1[i], arr2[j] <= 10⁹

Solution: Bit

(a[0] & b[i]) ^ (a[1] & b[i]) ^ … ^ (a[n-1] & b[i]) = (a[0] ^ a[1] ^ … ^ a[n-1]) & b[i]

We can pre compute that xor sum of array A.

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

C++

class Solution {

public:

int getXORSum(vector<int>& A, vector<int>& B) {

int ans = 0;

int xora = 0;

for (int a : A) xora ^= a;

for (int b : B) ans ^= (xora & b);

return ans;

}

};

花花酱 LeetCode 1834. Single-Threaded CPU

By zxi on April 18, 2021

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Solution: Simulation w/ Sort + PQ

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getOrder(vector<vector<int>>& tasks) {

const int n = tasks.size();

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

tasks[i].push_back(i);

sort(begin(tasks), end(tasks)); // sort by enqueue_time;

vector<int> ans;

priority_queue<pair<int, int>> q; // {-processing_time, -index}

int i = 0;

long t = 0;

while (ans.size() != n) {

// Advance to next enqueue time if q is empty.

if (i < n && q.empty() && tasks[i][0] > t)

t = tasks[i][0];

// Enqueue all available tasks.

while (i < n && tasks[i][0] <= t) {

q.emplace(-tasks[i][1], -tasks[i][2]);

++i;

}

// Extra the top one.

t -= q.top().first;

ans.push_back(-q.top().second);

q.pop();

}

return ans;

}

};

花花酱 LeetCode 1833. Maximum Ice Cream Bars

By zxi on April 18, 2021

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the i^th ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

Solution: Greedy

Sort by price in ascending order, buy from the lowest price to the highest price.

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

C++

class Solution {

public:

int maxIceCream(vector<int>& costs, int coins) {

sort(begin(costs), end(costs));

int ans = 0;

for (int c : costs) {

if (c > coins) break;

coins -= c;

++ans;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1838. Frequency of the Most Frequent Element

Solution: Sliding Window

C++

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

Solution: Base Conversion

C++

花花酱 LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND

Solution: Bit

C++

花花酱 LeetCode 1834. Single-Threaded CPU

Solution: Simulation w/ Sort + PQ

C++

花花酱 LeetCode 1833. Maximum Ice Cream Bars

Solution: Greedy

C++