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
updates = 0
for x in range(5, 0, -1):
used = min(counts[x], ceil(diff / x))
updates += used
diff -= used * x
if diff <= 0:
break
return updates
View More Similar Problems
Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h
View Solution →Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →