Appearance
question:Joy loves playing with arrays and numbers. She recently found another interesting problem. Given an array of n positive integers and a number k, she wants to find two distinct elements in the array such that their difference is exactly k. Write a program that finds any pair of elements in the array whose difference is exactly k. If no such pair exists, the program should output "No pair found". The input consists of two lines: - The first line contains two integers n and k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 10^6). - The second line contains n distinct positive integers, each not exceeding 10^6. The output should be a single line containing the two elements that have the exact difference of k, separated by a space. If there are multiple valid pairs, any one pair can be output. If no such pair exists, output "No pair found". # Sample Input 1: ``` 5 2 1 5 3 4 2 ``` # Sample Output 1: ``` 3 1 ``` (Note that there are other valid pairs like 5 and 3, 4 and 2) # Sample Input 2: ``` 3 10 8 1 7 ``` # Sample Output 2: ``` No pair found ``` # Explanation: In the first example, the pairs (3, 1), (5, 3), and (4, 2) have the exact difference of 2. Hence, the output can be any of these pairs. In the second example, no pair of elements have a difference of exactly 10, so the output is "No pair found".
answer:def find_pair_with_difference(n, k, arr): Finds a pair of elements in the array whose difference is exactly k. Parameters: n (int): The number of elements in the array k (int): The target difference arr (list): List of n integers Returns: tuple: A pair of integers from the array with the exact difference of k If no such pair is found, returns "No pair found" arr_set = set(arr) for num in arr: if num + k in arr_set: return (num, num + k) if num - k in arr_set: return (num, num - k) return "No pair found"
question:Implement a function that takes an array of integers and returns the length of the longest contiguous subarray with the same integer. For example, given the input array `[1, 2, 2, 2, 3, 3, 1, 1, 1, 1]`, the function should return `4`, since the longest contiguous subarray with the same integer is `[1, 1, 1, 1]`. The function should have the following signature: ```python def max_contiguous_subarray_length(arr: List[int]) -> int: pass ``` **Constraints:** - The length of the input array `arr` will be in the range `[1, 10^5]`. - Each element in the input array will be an integer in the range `[-10^9, 10^9]`. **Example:** ```python assert max_contiguous_subarray_length([1, 2, 2, 2, 3, 3, 1, 1, 1, 1]) == 4 assert max_contiguous_subarray_length([4, 4, 4, 4, 4, 4, 4, 4, 4, 4]) == 10 assert max_contiguous_subarray_length([1, 2, 3, 4, 5]) == 1 assert max_contiguous_subarray_length([3, 3, 3, 2, 2, 1]) == 3 ```
answer:def max_contiguous_subarray_length(arr): Returns the length of the longest contiguous subarray with the same integer. if not arr: return 0 max_length = 1 current_length = 1 for i in range(1, len(arr)): if arr[i] == arr[i - 1]: current_length += 1 else: if current_length > max_length: max_length = current_length current_length = 1 if current_length > max_length: max_length = current_length return max_length
question:Consider a forest represented as a 2D grid of size n times m. Each cell in the grid can either be empty '`.`' or contain a tree '`T`'. Gekko, the little animal, wants to build his treehouse over a connected area of trees. The treehouse must be a rectangular region such that all positions in this rectangle contain trees. You are given the grid and need to answer q queries. Each query checks if it is possible to find a rectangular region of size x times y completely covered by trees and if so, output the top-left corner of this rectangle. If multiple solutions exist, output the one with the smallest row index, and if there are still ties, the one with the smallest column index. If there is no such rectangular region, output `-1`. The first line contains three integers n, m, and q (1 leq n, m leq 500, 1 leq q leq 10^{3}) — the dimensions of the grid and the number of queries, respectively. The following n lines contain m characters each, representing the grid ('`.`' for empty cells and '`T`' for cells with trees). The next q lines contain two integers x and y (1 leq x leq n, 1 leq y leq m) — the dimensions of the treehouse to check for. For each query, output the row and column indices (1-based) of the top-left corner of the rectangular region if it exists, or `-1` if no such rectangle exists. # Example Input ``` 4 5 3 ..... .TTT. .TTT. ..T.. 2 2 1 3 3 2 ``` # Example Output ``` 2 2 2 2 -1 ``` # Explanation In the example, the grid is: ``` ..... .TTT. .TTT. ..T.. ``` For the first query, a 2x2 treehouse can be built starting at (2,2). For the second query, a 1x3 treehouse can be built starting at (2,2). For the third query, it is not possible to find a 3x2 region fully covered by trees.
answer:def find_treehouse(grid, n, m, x, y): Find the top-left corner of a rectangular region of size x by y that is fully covered by 'T' trees in the given grid. for i in range(n - x + 1): for j in range(m - y + 1): if all(grid[i + dx][j + dy] == 'T' for dx in range(x) for dy in range(y)): return i + 1, j + 1 # return 1-based index return -1 def solve(grid, n, m, queries): Process multiple queries on the given grid. results = [] for x, y in queries: result = find_treehouse(grid, n, m, x, y) results.append(result) return results
question:Write a program that simulates the merging of multiple sorted lists into a single sorted list. Given a list of k sorted integer lists, your task is to merge these k lists into a single sorted list. You need to implement a function that takes a single argument: - A list of k sorted integer lists, where 1 ≤ k ≤ 10⁴ and the length of each list is between 0 and 500. The function should return a single sorted list containing all the elements from the input lists. Example Input: [ [1, 4, 5], [1, 3, 4], [2, 6] ] Example Output: [1, 1, 2, 3, 4, 4, 5, 6] Explanation: You need to merge the sorted lists [1, 4, 5], [1, 3, 4], and [2, 6] to produce the final sorted list [1, 1, 2, 3, 4, 4, 5, 6].
answer:import heapq def merge_k_sorted_lists(lists): Merges k sorted integer lists into a single sorted list. Args: lists (List[List[int]]): A list of k sorted integer lists. Returns: List[int]: A single sorted list containing all elements from input lists. min_heap = [] for index, lst in enumerate(lists): if lst: heapq.heappush(min_heap, (lst[0], index, 0)) result = [] while min_heap: val, list_index, element_index = heapq.heappop(min_heap) result.append(val) if element_index + 1 < len(lists[list_index]): heapq.heappush(min_heap, (lists[list_index][element_index + 1], list_index, element_index + 1)) return result