Leetcode BiWeekly Contest, this week's biweekly contest, after two rounds of competition, let's write a solution for BiWeekly 19 Contest.
1342. Number of Steps to Reduce a Number to Zero#
Problem:
Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
Example:
Input: num = 14
Output: 6
Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
This problem is quite simple. Given a non-negative integer, we need to divide it by 2 if it's even, and subtract 1 if it's odd, until it becomes zero.
Here's a brute force solution:
class Solution:
def numberOfSteps(self, num: int) -> int:
count = 0
if num == 0:
return count
result = num
while result > 1:
if result % 2 == 0:
result = int(result / 2)
else:
result -= 1
count += 1
return count + 1
Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#
Problem:
Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
Example:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold)
Given an array and a length k, along with a threshold value, we need to find the number of sub-arrays in the array of size k whose average is greater than or equal to the threshold. This problem can be solved using a brute force approach, where we check each sub-array and calculate its average. However, this approach has a time complexity of O(M*K), where M is the length of the array, which can be inefficient.
To optimize the solution, we can use a trick. Let's assume the sum of the current i and the next k elements is sum[i]. We can use the following formula: sum[i] = sum[i-1] - arr[i] + arr[i+k-1]. This way, we can calculate the sum in constant time (O(1)). By using this optimization, the overall time complexity becomes O(N).
Here's the brute force solution:
from typing import List
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
if not arr:
return 0
length = len(arr)
sum_threshold = [0.0] * length
count = 0
last_index = length
for i in range(length - k, -1, -1):
if i == length - k:
total_sum = sum(arr[i:i + k])
else:
total_sum = sum_threshold[i + 1] - arr[last_index] + arr[i]
sum_threshold[i] = total_sum
if total_sum / k >= threshold:
count += 1
last_index -= 1
return count
1344. Angle Between Hands of a Clock#
Problem:
Given two numbers, hour and minutes. Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.
Example:
Input: hour = 12, minutes = 30
Output: 165
In this problem, we need to find the smaller angle between the hour and minute hands of a clock. To solve this, we can use the following knowledge:
-
A clock represents a circle, and the hour or minute hand completing a full rotation corresponds to an angle of 360°.
-
Each hour on the clock corresponds to an angle of 360°/12 = 30°.
-
For the hour hand, each minute corresponds to an angle of 360°/(12*60) = 0.5°.
-
For the minute hand, each minute corresponds to an angle of 360°/60 = 6°.
Here's the brute force solution:
class Solution:
def angleClock(self, hour: int, minutes: int) -> float:
hour %= 12
result = abs((minutes * 6) - (hour * 30 + minutes * 0.5))
return result if result < 360 else 360 - result
1345. Jump Game IV#
Problem:
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
- i + 1 where: i + 1 < arr.length.
- i - 1 where: i - 1 >= 0.
- j where: arr[i] == arr[j] and i != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
In this problem, we need to jump from the first index of the array to the last index using the following rules:
-
We can jump to index i + 1 if i + 1 < arr.length.
-
We can jump to index i - 1 if i - 1 >= 0.
-
We can jump to index j if arr[i] == arr[j] and i != j.
We need to find the minimum number of steps to reach the last index of the array, without jumping outside of the array at any time.
This problem can be solved using a breadth-first search (BFS) approach. We can create a dictionary where the keys are the values in the array and the values are lists of indices where those values occur. We can use a set to keep track of visited indices.
Starting from index 0, we can perform a BFS to find all the possible jumps from each index. We continue BFS until we reach the last index.
Here's the solution:
from typing import List, Set
import collections
class Solution:
def minJumps(self, arr: List[int]) -> int:
length = len(arr)
if not arr or length == 1:
return 0
value_index = collections.defaultdict(list)
for index, value in enumerate(arr):
value_index[value].append(index)
visited: Set[int] = set()
traversal_queue = collections.deque([(0, 0)])
result = 0
while traversal_queue:
next_step_queue = collections.deque()
for _ in range(len(traversal_queue)):
cur_index, cur_step = traversal_queue.popleft()
cur_value = arr[cur_index]
visited.add(cur_index)
for next_index in [cur_index + 1, cur_index - 1] + value_index[
cur_value
]:
if (length > next_index >= 0) and (next_index not in visited):
if next_index == length - 2:
return cur_step + 2
if next_index == length - 1:
return cur_step + 1
next_step_queue.append((next_index, cur_step + 1))
del value_index[cur_value]
traversal_queue = next_step_queue
return result
Conclusion#
This week's problems were not difficult, but required careful attention. For example, I made a mistake in the second problem by using a brute force approach and received a Time Limit Exceeded (TLE) error. In the third problem, I misread the question (it asked for the smaller angle) and received a Wrong Answer (WA). However, compared to the problems in the previous weekly contest, I consider myself lucky. The third problem in that contest made me lose my mind. I will write the solutions tomorrow.
Alright, time to go to sleep.