Bit Manipulation
Array
Dynamic Programming
Backtracking
Bitmask
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 <= 8
transactions[i].length == 3
0 <= fromi , toi < 12
fromi != toi
1 <= amounti <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 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 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 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 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 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 ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 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 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 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 ;
}
GitHub