A linear equation of two variables is defined as a * x + b * y = z. For an array of integers arr and some query value z, the minimum sum solution is the minimum possible value of a + b where 0 <= a, 0 <= b, and a * arr[i] + b * arr[j] = z. It is possible that i = j.
Given two arrays of integers arr and query, and an integer k, for each value in query, replace z in the linear equation with query[x] and find the minimum sum solution. Return an answer array where each answer[x] is the answer to query[x]. If the sum of a + b is less than or equal to k, answer[x] is a + b. Otherwise, it is -1.
Example
arr = [1, 2, 3, 6, 67]
query = [1, 4, 30, 7, 88]
k = 5
Output:
[1, 2, 5, 2, -1]For each query, choose non-negative integers a and b so that a * arr[i] + b * arr[j] = query[x] and minimize a + b. If no valid pair exists or the minimum sum exceeds k, return -1.
This problem asks for the minimum non-negative coefficient sum a + b such that a * arr[i] + b * arr[j] equals each query value, with the additional limit that a + b must not exceed k. Because k is small, the intended solution is to enumerate feasible coefficient pairs and use fast lookup to check whether the remaining value can be formed by an array element. Careful handling of zero coefficients, repeated use of the same array element, and impossible queries is essential.
