Huahua’s Tech Road

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

}

};

花花酱 LeetCode 2588. Count the Number of Beautiful Subarrays

By zxi on March 11, 2023

You are given a 0-indexed integer array nums. In one operation, you can:

Choose two different indices i and j such that 0 <= i, j < nums.length.
Choose a non-negative integer k such that the k^th bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
Subtract 2^k from nums[i] and nums[j].

A subarray is beautiful if it is possible to make all of its elements equal to 0 after applying the above operation any number of times.

Return the number of beautiful subarrays in the array nums.

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

Example 1:

Input: nums = [4,3,1,2,4]
Output: 2
Explanation: There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4].
- We can make all elements in the subarray [3,1,2] equal to 0 in the following way:
  - Choose [3, 1, 2] and k = 1. Subtract 2¹ from both numbers. The subarray becomes [1, 1, 0].
  - Choose [1, 1, 0] and k = 0. Subtract 2⁰ from both numbers. The subarray becomes [0, 0, 0].
- We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way:
  - Choose [4, 3, 1, 2, 4] and k = 2. Subtract 2² from both numbers. The subarray becomes [0, 3, 1, 2, 0].
  - Choose [0, 3, 1, 2, 0] and k = 0. Subtract 2⁰ from both numbers. The subarray becomes [0, 2, 0, 2, 0].
  - Choose [0, 2, 0, 2, 0] and k = 1. Subtract 2¹ from both numbers. The subarray becomes [0, 0, 0, 0, 0].

Example 2:

Input: nums = [1,10,4]
Output: 0
Explanation: There are no beautiful subarrays in nums.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

Solution: Hashtable + Prefix XOR

The problem is asking to find # of subarrays whose element wise xor is 0. We can use a hashtable to store the frequency of each prefix xor value, which reduces this problem to # of Subarray sum equal to k.

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

C++

// Author: Huahua

class Solution {

public:

long long beautifulSubarrays(vector<int>& nums) {

long long ans = 0;

unordered_map<int, int> m{{0, 1}};

int x = 0;

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

x ^= nums[i];

ans += m[x];

m[x] += 1;

}

return ans;

}

};

花花酱 LeetCode 2587. Rearrange Array to Maximize Prefix Score

By zxi on March 11, 2023

You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order).

Let prefix be the array containing the prefix sums of nums after rearranging it. In other words, prefix[i] is the sum of the elements from 0 to i in nums after rearranging it. The score of nums is the number of positive integers in the array prefix.

Return the maximum score you can achieve.

Example 1:

Input: nums = [2,-1,0,1,-3,3,-3]
Output: 6
Explanation: We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].
prefix = [2,5,6,5,2,2,-1], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.

Example 2:

Input: nums = [-2,-3,0]
Output: 0
Explanation: Any rearrangement of the array will result in a score of 0.

Constraints:

1 <= nums.length <= 10⁵
-10⁶ <= nums[i] <= 10⁶

Solution: Greedy

Sort the numbers in descending order.

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(vector<int>& nums) {

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

int ans = 0;

for (long i = 0, s = 0; i < nums.size(); ++i) {

s += nums[i];

if (s <= 0) break;

++ans;

}

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 2588. Count the Number of Beautiful Subarrays

Solution: Hashtable + Prefix XOR

C++

花花酱 LeetCode 2587. Rearrange Array to Maximize Prefix Score

Solution: Greedy

C++