Equalize List Sums with Minimal Updates - Amazon Top Interview Questions

Problem Statement :

```You are given two lists of integers a and b where every element in both lists is between 1 to 6. Consider an operation where you pick a number in either a or b and update its value to a number between 1 to 6.

Return the minimum number of operations required such that the sum of a and b are equal. If it's not possible, return -1.

Constraints

n ≤ 100,000 where n is the length of a
m ≤ 100,000 where m is the length of b

Example 1

Input

a = [1, 5]
b = [6, 5, 5]

Output
2

Explanation
If we change the 1 to 6 in a and the 6 to 1 in b, then both of their sums would be 11.

Example 2
Input
a = [6]
b = [1, 1, 1, 1, 1, 1, 1]
Output
-1
Explanation
There's no way to make a and b's sums equal.```

Solution :

```                        ```Solution in C++ :

int solve(vector<int>& A, vector<int>& B) {
if (max(A.size(), B.size()) > 6 * min(A.size(), B.size())) return -1;
sort(A.begin(), A.end());
sort(B.begin(), B.end());

int sum1 = 0, sum2 = 0;

for (int i : A) sum1 += i;
for (int i : B) sum2 += i;

if (sum1 > sum2) return solve(B, A);

// sum1 is always smaller
reverse(B.begin(), B.end());
int i = 0, j = 0;
int res = 0;

int dif = sum2 - sum1;
while (dif > 0) {
res++;
if (i < A.size() && j < B.size()) {
int a = 6 - A[i];
int b = B[j] - 1;
if (a > b) {
dif -= a;
i++;
} else {
dif -= b;
j++;
}
} else {
if (i < A.size()) {
dif -= (6 - A[i++]);
} else if (j < B.size()) {
dif -= (B[j++] - 1);
}
}
}
return res;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[] A, int[] B) {
int[] ops = new int[10]; // number of operations of each change value
int diff = Math.abs(sum(A) - sum(B));
if (sum(A) > sum(B)) {
for (int a : A) ops[a - 1] += 1;
for (int b : B) ops[6 - b] += 1;
} else {
for (int a : A) ops[6 - a] += 1;
for (int b : B) ops[b - 1] += 1;
}
int ans = 0;
int ind = 9;
// greedily pick the operation which causes the biggest change
while (ind > 0) {
while (ind > 0 && ops[ind] == 0) ind--;
if (diff <= 0)
break;
ans++;
diff -= ind;
ops[ind] -= 1;
}
if (diff <= 0) {
return ans;
} else {
return -1;
}
}

public int sum(int[] A) {
int s = 0;
for (int a : A) s += a;
return s;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, a, b):
if max(len(a), len(b)) > 6 * min(len(a), len(b)):
return -1

sum_a = sum(a)
sum_b = sum(b)
if sum_a > sum_b:
a, b = b, a
sum_a, sum_b = sum_b, sum_a

counts = [0] * 6
for x in a:
counts[6 - x] += 1
for x in b:
counts[x - 1] += 1

diff = sum_b - sum_a
for x in range(5, 0, -1):
used = min(counts[x], ceil(diff / x))
diff -= used * x
if diff <= 0:
break

```

Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element