Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/465.html
465. Optimal Account Balancing
Level
Hard
Description
A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill’s lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person’s ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
- A transaction will be given as a tuple (x, y, z). Note that
x ≠ yandz > 0. - Person’s IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
Input:
[[0,1,10], [2,0,5]]
Output:
2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:
Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
Output:
1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.
Solution
First loop over transactions and obtain each person’s remaining amount of money (either 0, positive or negative). Then do backtrack.
Starting from index 0 and transaction count 0, loop over each remaining amount after the start index. If a next amount has a different sign with the amount at the start index, then add the amount of the start index by the current amount with the number of transactions increased by 1, and do backtrack using the current index as the start index. If the end is reached, update the minimum number of transactions. Finally, return the minimum number of transactions.
-
class Solution { int minTransactions = Integer.MAX_VALUE; public int minTransfers(int[][] transactions) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int[] transaction : transactions) { int person1 = transaction[0], person2 = transaction[1], amount = transaction[2]; int value1 = map.getOrDefault(person1, 0) - amount; int value2 = map.getOrDefault(person2, 0) + amount; map.put(person1, value1); map.put(person2, value2); } int groupSize = map.size(); int[] balances = new int[groupSize]; Set<Integer> keySet = map.keySet(); int index = 0; for (int key : keySet) { int balance = map.get(key); balances[index++] = balance; } backtrack(balances, 0, 0); return minTransactions; } public void backtrack(int[] balances, int start, int count) { int length = balances.length; while (start < length && balances[start] == 0) start++; if (start == length) minTransactions = Math.min(minTransactions, count); else { boolean positive = balances[start] > 0; for (int i = start + 1; i < length; i++) { if ((balances[i] > 0) ^ positive) { balances[i] += balances[start]; backtrack(balances, start + 1, count + 1); balances[i] -= balances[start]; } } } } } -
class Solution(object): def minTransfers(self, transactions): balances = collections.defaultdict(int) people = set() for giver, receiver, amount in transactions: balances[giver] -= amount balances[receiver] += amount people |= {giver, receiver} for person, balance in balances.items(): if balance == 0: people.discard(person) del balances[person] people_list = list(people) def dfs(people_list): if not people_list: return 0 people = set(people_list) for i in range(2, len(people_list) + 1): for persons in itertools.combinations(people_list, i): if sum(balances[p] for p in persons) == 0: people -= set(persons) return dfs(list(people)) + len(persons) - 1 return dfs(people_list) -
class Solution { public: int minTransfers(vector<vector<int>>& transactions) { int g[12]{}; for (auto& t : transactions) { g[t[0]] -= t[2]; g[t[1]] += t[2]; } vector<int> nums; for (int x : g) { if (x) { nums.push_back(x); } } int m = nums.size(); int f[1 << m]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i < 1 << m; ++i) { int s = 0; for (int j = 0; j < m; ++j) { if (i >> j & 1) { s += nums[j]; } } if (s == 0) { f[i] = __builtin_popcount(i) - 1; for (int j = (i - 1) & i; j; j = (j - 1) & i) { f[i] = min(f[i], f[j] + f[i ^ j]); } } } return f[(1 << m) - 1]; } }; -
func minTransfers(transactions [][]int) int { g := [12]int{} for _, t := range transactions { g[t[0]] -= t[2] g[t[1]] += t[2] } nums := []int{} for _, x := range g { if x != 0 { nums = append(nums, x) } } m := len(nums) f := make([]int, 1<<m) for i := 1; i < 1<<m; i++ { f[i] = 1 << 29 s := 0 for j, x := range nums { if i>>j&1 == 1 { s += x } } if s == 0 { f[i] = bits.OnesCount(uint(i)) - 1 for j := (i - 1) & i; j > 0; j = (j - 1) & i { f[i] = min(f[i], f[j]+f[i^j]) } } } return f[1<<m-1] } func min(a, b int) int { if a < b { return a } return b } -
function minTransfers(transactions: number[][]): number { const g: number[] = new Array(12).fill(0); for (const [f, t, x] of transactions) { g[f] -= x; g[t] += x; } const nums = g.filter(x => x !== 0); const m = nums.length; const f: number[] = new Array(1 << m).fill(1 << 29); f[0] = 0; for (let i = 1; i < 1 << m; ++i) { let s = 0; for (let j = 0; j < m; ++j) { if (((i >> j) & 1) === 1) { s += nums[j]; } } if (s === 0) { f[i] = bitCount(i) - 1; for (let j = (i - 1) & i; j; j = (j - 1) & i) { f[i] = Math.min(f[i], f[j] + f[i ^ j]); } } } return f[(1 << m) - 1]; } function bitCount(i: number): number { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }