Appearance
question:An advanced binary search algorithm is typically used to quickly find elements or solve problems involving sorted data. One common application is finding the minimum value that satisfies a certain condition. Consider the following problem: You are given a sorted array of integers and a target integer `x`. Write a function to find and return the smallest integer in the array that is greater than or equal to `x`. If no such element exists, return `-1`. Function Signature: ```python def find_min_gte(arr: List[int], x: int) -> int: ``` Input: - `arr` (1 ≤ len(arr) ≤ 10^5): a sorted list of integers (-10^9 ≤ arr[i] ≤ 10^9) - `x` (-10^9 ≤ x ≤ 10^9): the target integer Output: - an integer representing the smallest integer in the array that is greater than or equal to `x`, or `-1` if no such element exists. Examples: ```python assert find_min_gte([1, 2, 3, 4, 5], 3) == 3 assert find_min_gte([1, 2, 3, 4, 5], 6) == -1 assert find_min_gte([-3, -1, 0, 3, 4], -2) == -1 assert find_min_gte([10, 20, 30, 40], 25) == 30 ``` Explanation: In the first example, the smallest integer greater than or equal to `3` is `3`. In the second example, there is no integer greater than or equal to `6`, so it returns `-1`. In the third example, there is no integer greater than or equal to `-2`, so it returns `-1`. The fourth example returns `30` because it is the smallest integer in the array which is greater than `25`. Constraints: - You can assume the input list is sorted in non-descending order. - Your solution must run in O(log n) time complexity.
answer:from typing import List def find_min_gte(arr: List[int], x: int) -> int: Finds the smallest integer in the array that is greater than or equal to x. If no such integer exists, returns -1. left, right = 0, len(arr) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if arr[mid] >= x: result = arr[mid] right = mid - 1 else: left = mid + 1 return result if result != -1 else -1
question:Alice and Bob are playing a game on a 2D grid. The grid is an n x n matrix where each cell contains one of two values: a 1 or a 0. Alice starts at the top-left corner of the grid (position (0, 0)) and wants to reach the bottom-right corner of the grid (position (n-1, n-1)). She can only move to the right or down at each step. However, she can only step on cells that contain a 1. Bob, on the other hand, can change up to k cells in the grid from 1 to 0 before Alice starts her journey. His goal is to make it impossible for Alice to reach her destination. Write a function `bob_can_block` that determines whether Bob can change up to k cells to block Alice from reaching the bottom-right corner of the grid. Function Signature: `def bob_can_block(grid: List[List[int]], k: int) -> bool:` Input: - `grid` (List[List[int]]): A 2D list of integers representing the grid (1s and 0s). - `k` (int): The number of cells Bob can change from 1 to 0. Output: - Return `True` if Bob can block Alice from reaching the bottom-right corner; otherwise, return `False`. Constraints: - 1 <= n <= 10 - 0 <= k <= n^2 Example Input: grid = [ [1, 1, 0, 1], [1, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1] ] k = 2 Example Output: True Explanation: Bob can change the cells at positions (1, 2) and (3, 1) from 1 to 0. This will block any possible path for Alice from (0, 0) to (3, 3). Hence, the function returns True.
answer:def bob_can_block(grid, k): Determines if Bob can block Alice from reaching the bottom-right corner by changing up to k cells from 1 to 0. n = len(grid) def is_reachable(): from collections import deque directions = [(1, 0), (0, 1)] queue = deque([(0, 0)]) visited = set((0, 0)) while queue: x, y = queue.popleft() if (x, y) == (n-1, n-1): return True for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] == 1: queue.append((nx, ny)) visited.add((nx, ny)) return False if not is_reachable(): return True ones_positions = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1 and (i != 0 or j != 0) and (i != n-1 or j != n-1)] from itertools import combinations for positions in combinations(ones_positions, k): for x, y in positions: grid[x][y] = 0 if not is_reachable(): return True for x, y in positions: grid[x][y] = 1 return False
question:STATEMENT You are given a list of N integers where each integer can belong to either of the two categories: positive or negative. You need to sort the list in such a way that all positive integers come before all negative integers, while preserving the relative order of the integers within their respective categories. INPUT The first line will contain an integer T, denoting the number of test cases. Each test case contains two lines. The first line of each test case will contain an integer N, the size of the list. The second line of each test case contains N space-separated integers which make up the list. 1 <= T <= 100 1 <= N <= 1000 -1000 <= integers in the list <= 1000 OUTPUT For each test case, print one line containing the rearranged list of integers. EXAMPLE INPUT 2 6 -1 2 -3 4 -5 6 4 7 -8 9 -10 OUTPUT 2 4 6 -1 -3 -5 7 9 -8 -10
answer:def sort_pos_neg(arr): This function takes a list of integers and returns a new list with all positive integers before all negative integers, while preserving the relative order of the integers within their respective categories. positives = [x for x in arr if x >= 0] negatives = [x for x in arr if x < 0] return positives + negatives def rearrange_lists(test_cases): This function takes a list of test case tuples and prints the rearranged lists as per the conditions. Each tuple contains the size of the list and the list itself. results = [] for N, arr in test_cases: rearranged = sort_pos_neg(arr) results.append(rearranged) return results
question:You are given an array A consisting of N integers. Your goal is to find the sum of the maximum and minimum element in every contiguous subarray of length K from A. Write a function to solve this problem. Function Signature: ```python def sum_of_min_max(A: List[int], K: int) -> List[int]: ``` # Input * The first line contains an integer N, the number of elements in the array A. * The second line contains N integers, the elements of array A. * The third line contains an integer K, the length of the subarrays. 1. 1 ≤ N ≤ 100,000 2. 1 ≤ A[i] ≤ 1,000,000 (1 ≤ i ≤ N) 3. 1 ≤ K ≤ N # Output * Return a list of integers, where the i-th integer is the sum of the maximum and minimum element in the subarray A[i:i+K]. # Example **Input** ``` 7 2 5 1 8 10 6 3 3 ``` **Output** ``` [6, 6, 9, 16, 16] ``` **Explanation** The contiguous subarrays of length 3 are: * [2, 5, 1] -> max(2, 5, 1) + min(2, 5, 1) = 5 + 1 = 6 * [5, 1, 8] -> max(5, 1, 8) + min(5, 1, 8) = 8 + 1 = 9 * [1, 8, 10] -> max(1, 8, 10) + min(1, 8, 10) = 10 + 1 = 11 * [8, 10, 6] -> max(8, 10, 6) + min(8, 10, 6) = 10 + 6 = 16 * [10, 6, 3] -> max(10, 6, 3) + min(10, 6, 3) = 10 + 3 = 13
answer:from collections import deque from typing import List def sum_of_min_max(A: List[int], K: int) -> List[int]: n = len(A) if K > n or K == 0: return [] min_deque, max_deque = deque(), deque() result = [] for i in range(K): while min_deque and A[min_deque[-1]] >= A[i]: min_deque.pop() while max_deque and A[max_deque[-1]] <= A[i]: max_deque.pop() min_deque.append(i) max_deque.append(i) for i in range(K, n): result.append(A[min_deque[0]] + A[max_deque[0]]) while min_deque and min_deque[0] <= i - K: min_deque.popleft() while max_deque and max_deque[0] <= i - K: max_deque.popleft() while min_deque and A[min_deque[-1]] >= A[i]: min_deque.pop() while max_deque and A[max_deque[-1]] <= A[i]: max_deque.pop() min_deque.append(i) max_deque.append(i) result.append(A[min_deque[0]] + A[max_deque[0]]) return result