Minimum Number of Transfers to Settle Debts - Google Top Interview Questions


Problem Statement :


You are given a two-dimensional list of integers transfers containing [source, dest, amount], which means that person source lent person dest a dollar amount equal to amount. Return the minimum number of person-to-person transfers that are required so that all debts are paid.

Constraints

n ≤ 13 where n is the number of participants

Example 1

Input

transfers = [

    [0, 1, 50],

    [1, 2, 50]

]

Output

1

Explanation

Person 0 gave person 1 $50 and person 1 gave person 2 $50.

So person 2 can directly give $50 to person 0.


Solution :



title-img 




                        Solution in C++ :

int solve(vector<vector<int>>& transfers) {
    map<int, int> M;
    for (auto e : transfers) {
        M[e[0]] -= e[2];
        M[e[1]] += e[2];
    }
    vector<int> arr;
    for (auto e : M) {
        if (e.second) {
            arr.push_back(e.second);
        }
    }
    int n = arr.size();
    int i, j;
    vector<int> parts;
    for (i = 1; i < (1 << n); ++i) {
        int s = 0;
        for (j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                s += arr[j];
            }
        }
        if (s == 0) {
            parts.push_back(i);
        }
    }
    vector<int> dp(1 << n, 1e9);
    dp[0] = 0;
    for (i = 1; i < (1 << n); ++i) {
        for (int x : parts) {
            if ((i & x) == x) {
                dp[i] = min(dp[i], dp[i - x] + __builtin_popcount(x) - 1);
            }
        }
    }
    return dp[(1 << n) - 1];
}
                    




                        Solution in Python : 
                            
class Solution:
    def solve(self, transfers):
        acc = Counter()

        for u, v, val in transfers:
            acc[u] += val
            acc[v] -= val

        @cache
        def search(rem):

            if len(rem) == 2:
                if rem[0] == 0:
                    return 0
                return 1

            curr = rem[0]

            if curr == 0:
                return search(rem[1:])

            best = 30

            for i, val in enumerate(rem[1:]):
                if (curr < 0 and val > 0) or (curr > 0 and val < 0):
                    next_state = tuple(
                        sorted(rem[1 : i + 1] + rem[i + 2 :] + (val + curr,), key=abs)
                    )
                    best = min(best, 1 + search(next_state))

            return best

        return search(tuple(sorted(acc.values(), key=abs)))


View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →