Weekly Contest 487

Contest Information

Problems

Q1. Count Monobit Integers

Problem Description

You are given an integer n.

An integer is called Monobit if all bits in its binary representation are the same.

Return the count of Monobit integers in the range [0, n] (inclusive).

Example 1:

Input: n = 1

Output: 2

Explanation:

• The integers in the range [0, 1] have binary representations "0" and "1".
• Each representation consists of identical bits. Thus, the answer is 2.

Example 2:

Input: n = 4

Output: 3

Explanation:

• The integers in the range [0, 4] include binaries "0", "1", "10", "11", and "100".
• Only 0, 1 and 3 satisfy the Monobit condition. Thus, the answer is 3.

Constraints:

• 0 <= n <= 1000

def countMonobitIntegers(n):
  count = 1  # 0 is always monobit
  num = 1    # Start with 1 (binary: "1")
  while num <= n:
    count += 1
    num = num * 2 + 1  # Next all-1s number
  return count

Q2. Final Element After Subarray Deletions

Problem Description

You are given an integer array nums.

Two players, Alice and Bob, play a game in turns, with Alice playing first.

• In each turn, the current player chooses any subarray nums[l..r] such that r - l + 1 < m, where m is the current length of the array.
• The selected subarray is removed, and the remaining elements are concatenated to form the new array.
• The game continues until only one element remains.

Alice aims to maximize the final element, while Bob aims to minimize it. Assuming both play optimally, return the value of the final remaining element.

Example 1:

Input: nums = [1,5,2]

Output: 2

Explanation:

• Alice removes [1], array becomes [5, 2].
• Bob removes [5], array becomes [2]. Thus, the answer is 2.

Example 2:

Input: nums = [3,7]

Output: 7

Explanation: Alice removes [3], leaving the array [7]. Since Bob cannot play a turn now, the answer is 7.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

def finalElement(nums):
  n = len(nums)
  nums_sorted = sorted(nums)
  # With optimal play, result depends on parity
  if (n - 1) % 2 == 1:  # Alice has last move
    return nums_sorted[(n - 1) // 2 + 1]
  else:  # Bob has last move
    return nums_sorted[(n - 1) // 2]

Q3. Design Ride Sharing System

Problem Description

A ride sharing system manages ride requests from riders and availability from drivers. Riders request rides, and drivers become available over time. The system should match riders and drivers in the order they arrive.

Implement the RideSharingSystem class:

• RideSharingSystem() Initializes the system.
• void addRider(int riderId) Adds a new rider with the given riderId.
• void addDriver(int driverId) Adds a new driver with the given driverId.
• int[] matchDriverWithRider() Matches the earliest available driver with the earliest waiting rider and removes both of them from the system. Returns [driverId, riderId] if a match is made, [-1, -1] otherwise.
• void cancelRider(int riderId) Cancels the ride request of the rider with the given riderId if the rider exists and has not yet been matched.

Constraints:

• 1 <= riderId, driverId <= 1000
• Each riderId is unique among riders and is added at most once.
• Each driverId is unique among drivers and is added at most once.
• At most 1000 calls will be made in total.

from collections import deque

class RideSharingSystem:
  def __init__(self):
    self.riders = deque()
    self.drivers = deque()
    self.cancelled = set()
    self.matched_riders = set()

  def addRider(self, riderId):
    self.riders.append(riderId)

  def addDriver(self, driverId):
    self.drivers.append(driverId)

  def matchDriverWithRider(self):
    # Remove cancelled riders from front
    while self.riders and self.riders[0] in self.cancelled:
      self.cancelled.remove(self.riders.popleft())

    if not self.riders or not self.drivers:
      return [-1, -1]

    driver = self.drivers.popleft()
    rider = self.riders.popleft()
    self.matched_riders.add(rider)
    return [driver, rider]

  def cancelRider(self, riderId):
    if riderId not in self.matched_riders:
      self.cancelled.add(riderId)

Q4. Longest Alternating Subarray After Removing At Most One Element

Problem Description

You are given an integer array nums.

A subarray nums[l..r] is alternating if one of the following holds:

• nums[l] < nums[l + 1] > nums[l + 2] < nums[l + 3] > ...
• nums[l] > nums[l + 1] < nums[l + 2] > nums[l + 3] < ...

You can remove at most one element from nums. Then, you select an alternating subarray from nums.

Return the maximum length of the alternating subarray you can select.

Example 1:

Input: nums = [2,1,3,2]

Output: 4

Explanation: The entire array [2, 1, 3, 2] is alternating because 2 > 1 < 3 > 2.

Example 2:

Input: nums = [3,2,1,2,3,2,1]

Output: 4

Explanation: Remove nums[3]. The array becomes [3, 2, 1, 3, 2, 1]. Select subarray [2, 1, 3, 2].

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

def longestAlternatingSubarray(nums):
  n = len(nums)
  if n <= 2:
    return n if n == 1 or nums[0] != nums[1] else 1

  # left[i] = length of alternating subarray ending at i
  left = [1] * n
  for i in range(1, n):
    if (left[i-1] % 2 == 1 and nums[i] != nums[i-1]) or \
       (left[i-1] % 2 == 0 and ((left[i-1] // 2) % 2 == 0) != (nums[i] > nums[i-1])):
      # Check alternating pattern continues
      if (left[i-1] == 1 and nums[i] != nums[i-1]) or \
         (left[i-1] > 1 and isAlternating(nums, i-left[i-1]+1, i)):
        left[i] = left[i-1] + 1

  # Similar for right[i]
  right = [1] * n
  for i in range(n-2, -1, -1):
    if nums[i] != nums[i+1]:
      if canExtendRight(nums, i, right[i+1]):
        right[i] = right[i+1] + 1

  ans = max(left)

  # Try removing each element
  for i in range(1, n-1):
    if canMerge(nums, i, left[i-1], right[i+1]):
      ans = max(ans, left[i-1] + right[i+1])

  return ans