Description
You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.
Return the minimum number of transactions required to settle the debt.
Example 1:
Input: transactions = [[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: transactions = [[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.
Constraints:
1 <= transactions.length <= 8transactions[i].length == 30 <= fromi, toi < 12fromi != toi1 <= amounti <= 100
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
g = defaultdict(int)
for f, t, x in transactions:
g[f] -= x
g[t] += x
nums = [x for x in g.values() if x]
m = len(nums)
f = [inf] * (1 << m)
f[0] = 0
for i in range(1, 1 << m):
s = 0
for j, x in enumerate(nums):
if i >> j & 1:
s += x
if s == 0:
f[i] = i.bit_count() - 1
j = (i - 1) & i
while j > 0:
f[i] = min(f[i], f[j] + f[i ^ j])
j = (j - 1) & i
return f[-1](code-box)
class Solution {
public int minTransfers(int[][] transactions) {
int[] g = new int[12];
for (var t : transactions) {
g[t[0]] -= t[2];
g[t[1]] += t[2];
}
List<Integer> nums = new ArrayList<>();
for (int x : g) {
if (x != 0) {
nums.add(x);
}
}
int m = nums.size();
int[] f = new int[1 << m];
Arrays.fill(f, 1 << 29);
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) == 1) {
s += nums.get(j);
}
}
if (s == 0) {
f[i] = Integer.bitCount(i) - 1;
for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
f[i] = Math.min(f[i], f[j] + f[i ^ j]);
}
}
}
return f[(1 << m) - 1];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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;
}(code-box)
