Huahua’s Tech Road

花花酱 LeetCode 2644. Find the Maximum Divisibility Score

By zxi on April 28, 2023

You are given two 0-indexed integer arrays nums and divisors.

The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].

Return the integer divisors[i] with the maximum divisibility score. If there is more than one integer with the maximum score, return the minimum of them.

Example 1:

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score of divisors[1] is 1 since nums[0] is divisible by 2.
The divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.
Since divisors[2] has the maximum divisibility score, we return it.

Example 2:

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.
Since divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).

Example 3:

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.
The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.
Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).

Constraints:

1 <= nums.length, divisors.length <= 1000
1 <= nums[i], divisors[i] <= 10⁹

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int maxDivScore(vector<int>& nums, vector<int>& divisors) {

int maxScore = 0;

int ans = INT_MAX;

for (int d : divisors) {

int score = 0;

for (int x : nums) {

score += x % d == 0;

}

if (score > maxScore) {

maxScore = score;

ans = d;

}

if (score == maxScore)

ans = min(ans, d);

}

return ans;

}

};

花花酱 LeetCode 2643. Row With Maximum Ones

By zxi on April 28, 2023

Given a m x n binary matrix mat, find the 0-indexed position of the row that contains the maximum count of ones, and the number of ones in that row.

In case there are multiple rows that have the maximum count of ones, the row with the smallest row number should be selected.

Return an array containing the index of the row, and the number of ones in it.

Example 1:

Input: mat = [[0,1],[1,0]]
Output: [0,1]
Explanation: Both rows have the same number of 1's. So we return the index of the smaller row, 0, and the maximum count of ones (1). So, the answer is [0,1].

Example 2:

Input: mat = [[0,0,0],[0,1,1]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So we return its index, 1, and the count. So, the answer is [1,2].

Example 3:

Input: mat = [[0,0],[1,1],[0,0]]
Output: [1,2]
Explanation: The row indexed 1 has the maximum count of ones (2). So the answer is [1,2].

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.

Solution: Counting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {

vector<int> ans(2);

for (int i = 0; i < mat.size(); ++i) {

int ones = accumulate(begin(mat[i]), end(mat[i]), 0);

if (ones > ans[1]) {

ans[0] = i;

ans[1] = ones;

}

return ans;

}

};

花花酱 LeetCode 2653. Sliding Subarray Beauty

By zxi on April 27, 2023

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the x^th smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3. 
The first subarray is [1, -1, -3] and the 2^nd smallest negative integer is -1. 
The second subarray is [-1, -3, -2] and the 2^nd smallest negative integer is -2. 
The third subarray is [-3, -2, 3] and the 2^nd smallest negative integer is -2.

Example 2:

Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2^nd smallest negative integer is -1.
For [-2, -3], the 2^nd smallest negative integer is -2.
For [-3, -4], the 2^nd smallest negative integer is -3.
For [-4, -5], the 2^nd smallest negative integer is -4.

Example 3:

Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1^st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1^st smallest negative integer is -3.
For [-3, 0], the 1^st smallest negative integer is -3.
For [0, -3], the 1^st smallest negative integer is -3.

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Solution: Sliding Window + Counter

Since the range of nums are very small (-50 ~ 50), we can use a counter to track the frequency of each element, s.t. we can find the k-the smallest element in O(50) instead of O(k).

Time complexity: O((n – k + 1) * 50)
Space complexity: O(50)

C++

// Author: Huahua

class Solution {

public:

vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {

constexpr int kMax = 50;

const int n = nums.size();

vector<int> counts(2 * kMax + 1);

vector<int> ans;

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

if (i >= k)

--counts[nums[i - k] + kMax];

++counts[nums[i] + kMax];

if (i >= k - 1) {

int b = 0;

for (int j = 0, s = 0; j <= kMax; ++j) {

s += counts[j];

if (s >= x) {

b = j - kMax;

break;

}

ans.push_back(b);

}

return ans;

}

};

花花酱 LeetCode 2652. Sum Multiples

By zxi on April 27, 2023

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, or 7.

Return an integer denoting the sum of all numbers in the given range satisfying the constraint.

Example 1:

Input: n = 7
Output: 21
Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.

Example 2:

Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

Example 3:

Input: n = 9
Output: 30
Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.

Constraints:

1 <= n <= 10³

Solution: Mod

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

C++

// Author: Huahua

class Solution {

public:

int sumOfMultiples(int n) {

int ans = 0;

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

if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)

ans += i;

}

return ans;

}

};

花花酱 LeetCode 2651. Calculate Delayed Arrival Time

By zxi on April 27, 2023

You are given a positive integer arrivalTime denoting the arrival time of a train in hours, and another positive integer delayedTime denoting the amount of delay in hours.

Return the time when the train will arrive at the station.

Note that the time in this problem is in 24-hours format.

Example 1:

Input: arrivalTime = 15, delayedTime = 5 
Output: 20 
Explanation: Arrival time of the train was 15:00 hours. It is delayed by 5 hours. Now it will reach at 15+5 = 20 (20:00 hours).

Example 2:

Input: arrivalTime = 13, delayedTime = 11
Output: 0
Explanation: Arrival time of the train was 13:00 hours. It is delayed by 11 hours. Now it will reach at 13+11=24 (Which is denoted by 00:00 in 24 hours format so return 0).

Constraints:

1 <= arrivaltime < 24
1 <= delayedTime <= 24

Solution: Mod 24

C++

// Author: Huahua

class Solution {

public:

int findDelayedArrivalTime(int arrivalTime, int delayedTime) {

return (arrivalTime + delayedTime) % 24;

}

};

Huahua's Tech Road

花花酱 LeetCode 2644. Find the Maximum Divisibility Score

Solution: Brute Force

C++

花花酱 LeetCode 2643. Row With Maximum Ones

Solution: Counting

C++

花花酱 LeetCode 2653. Sliding Subarray Beauty

Solution: Sliding Window + Counter

C++

花花酱 LeetCode 2652. Sum Multiples

Solution: Mod

C++

花花酱 LeetCode 2651. Calculate Delayed Arrival Time

Solution: Mod 24

C++