Create viral videos with

GPT-4o + Ads library

Use GPT-4o to edit video empowered by Youtube & Tiktok & Facebook ads library. Turns your links or media assets into viral videos in one click.

Try it free

#Education

Hello everyone, my name is Karan Masu, and welcome to this video where we will discuss the solutions for the weekly coding contest. Let's dive into the breakdown of the questions and solutions provided in this contest.

**Description:**
Bob is in his university hostel where Alice calls and invites him to the cafeteria located at a distance d meters from his hostel. Bob has two options to travel this distance: walking or biking. The objective is to determine which mode of transportation will get Bob to Alice faster.

**Approach:**

- Bob can walk at a constant speed of x meters per second.
- Bob can ride his bike at a constant speed of y meters per second but loses k seconds due to interruptions from friends.
- We need to compare the times taken by walking and biking:
- Time taken by walking: (T_1 = \frac(d)(x))
- Time taken by biking: (T_2 = \frac(d)(y) + k)

**Solution:**

If `T1`

is less than or equal to `T2`

, Bob should walk. Otherwise, he should bike. Here’s a simplified implementation in Python:

```
def reach_alice(d, x, y, k):
T1 = d / x
T2 = d / y + k
if T1 <= T2:
return "walk"
else:
return "bike"
```

**Description:**
Bob plays a game with his students involving selecting numbers from a board based on a string STR of binary values. Depending on whether the character in the string is '0' or '1', a girl (selects the minimum) or a boy (selects the maximum) will choose a number from the board, respectively.

**Approach:**

- Short the array.
- Use two pointers technique to point to the smallest and largest available numbers.
- Traverse the string and keep updating the array based on the values (0 or 1).
- Maintain a result list to keep track of selections.

**Solution:**

Here’s the implementation in Python:

```
def bobs_game(arr, str):
arr.sort()
min_pointer = 0
max_pointer = len(arr) - 1
result = []
for char in str:
if char == '0':
result.append(arr[min_pointer])
min_pointer += 1
else:
result.append(arr[max_pointer])
max_pointer -= 1
return result
```

**Description:**
You are given an array `ARR`

consisting of `n`

integers. A subarray is called beautiful if the sum of the minimum and maximum elements of that subarray is divisible by the length of the subarray. The task is to count the number of beautiful subarrays.

**Approach:**

- The value of array elements is between 1 and 26.
- Only check subarrays whose length is between 1 and 52 since the maximum value of minimum + maximum (52) determines that lengths beyond this range can never divide it.
- For every starting point of the subarray, calculate the minimum and maximum and check the condition.

**Solution:**

Here’s the optimized implementation to handle large arrays:

```
def beautiful_subarrays(arr):
n = len(arr)
result = 0
for i in range(n):
min_val = float('inf')
max_val = float('-inf')
for j in range(i, min(i + 52, n)): # Check only till max length 52
min_val = min(min_val, arr[j])
max_val = max(max_val, arr[j])
if (min_val + max_val) % (j - i + 1) == 0:
result += 1
return result
```

**Description:**
A restaurant menu has `n`

items with specified prices. Given several queries of two types, modify the prices accordingly and compute the sum of prices after each query:

**Type 1**(1 x -1): Add`x`

to the prices of all items.**Type 2**(2 x y): Change the prices of items priced`x`

to`y`

.

**Approach:**

- For Type 1 queries: Accumulate additions in a variable to avoid direct manipulation on each item.
- For Type 2 queries: Use a lookup table (hash map) to keep the count of item prices and process changes efficiently.

**Solution:**

The implementation is optimized using a hash table and a lazy update approach:

```
def restaurant_queries(prices, queries):
total_sum = sum(prices)
count_map = ()
add = 0
for price in prices:
count_map[price] = count_map.get(price, 0) + 1
results = []
for query in queries:
if query[0] == 1: # Type 1
x = query[1]
add += x
total_sum += len(prices) * x
elif query[0] == 2: # Type 2
x = query[1] - add
y = query[2] - add
if x in count_map:
count = count_map[x]
total_sum = total_sum - (count * (x + add)) + (count * (y + add))
count_map[y] = count_map.get(y, 0) + count
del count_map[x]
results.append(total_sum)
return results
```

- Transportation Optimization
- Array Manipulation
- Subarray Calculation
- Hash Map
- Lazy Update
- Python Implementation

The lazy update technique involves maintaining an "add" variable that tracks the cumulative additions to each item's price without actually updating the array. This helps in handling multiple update queries efficiently.

The subarray length is capped at 52 because the elements' range is between 1 and 26, making their sum maximum 52. Lengths beyond this cannot divide sums in the range of 2 to 52.

The two-pointer technique helps efficiently choose the smallest or largest available number from a sorted list as required by the game rules.

`count_map[x - add]`

and `count_map[y - add]`

in Restaurant Queries?These updates reflect the effective counts of elements considering the cumulative additions by Type 1 queries, ensuring accurate modifications and calculations for Type 2 queries.

That's a wrap-up of the solutions and explanations for the GFG Weekly Coding Contest - 164. I hope these insights help you understand and solve similar problems efficiently. Happy coding!

In addition to the incredible tools mentioned above, for those looking to elevate their video creation process even further, Topview.ai stands out as a revolutionary online AI video editor.

TopView.ai provides two powerful tools to help you make ads video in one click.

Materials to Video: you can upload your raw footage or pictures, TopView.ai will edit video based on media you uploaded for you.

Link to Video: you can paste an E-Commerce product link, TopView.ai will generate a video for you.

You may also like