# Share My O(N!) NPC solution, TLE for large case

• ``````import java.util.*;

public class Solution {
public int minTransfers(int[][] trans) {
Map<Integer, Integer> net = new HashMap<>();
for(int i = 0; i < trans.length; i++){
net.put(trans[i][0], net.getOrDefault(trans[i][0], 0) - trans[i][2]);
net.put(trans[i][1], net.getOrDefault(trans[i][1], 0) + trans[i][2]);
}
int[] temp = new int[net.size()];
int i = 0;
for(int j : net.values()){
if(j != 0)temp[i++] = j;
}
int[] a = new int[i];
System.arraycopy(temp, 0, a, 0, i);
transactions.clear();
number = Integer.MAX_VALUE;
mintran(a, 0);
return number;
}

private List<int[]> transactions = new ArrayList<>();
private int number = Integer.MAX_VALUE;

private void mintran(int[] a, int start){
//System.out.println(Arrays.toString(a));
if(transactions.size() >= number) return;
if(number == (a.length + 1)/2) return;

if(a.length < 2){
number = 0;
return;
}else if(a.length == 2) {
number = a[0] == 0 ? 0 : 1;
return;
}else{
int ind = -1;
int max = Integer.MIN_VALUE;
int i = start;
for(; i < a.length; i++){
if(Math.abs(a[i]) > max){
max = Math.abs(a[i]);
ind = i;
}
}

if(max == 0 || start == a.length){
if(transactions.size() < number){
number = transactions.size();
}
return;
}

int temp = a[ind];
a[ind] = a[start];
a[start] = temp;

for(i = start + 1; i < a.length; i++){
if(a[i] * a[start] < 0) {
temp = a[i];
a[i] += a[start];
mintran(a, start + 1);
a[i] = temp;
transactions.remove(transactions.size()-1);
}
}

temp = a[ind];
a[ind] = a[start];
a[start] = temp;

}
}

public static void main(String[] args) {
int[][] A = new int[][] {{0,1,1}, {2,3,2}, {4,5,3}, {6,7,4}, {8,9,5}, {10,11,6}, {12,13,7}, {14,15,2}, {14,16,2}, {14,17,2}, {14,18,2}};
Solution solution = new Solution();
System.out.println(solution.minTransfers(A));
}
}
``````

• Lol
Thank you for sharing.

• @fatalme

It seems your code also fails on the following test case(should be 11 instead of 14):

[[0,1,1],[2,3,2],[4,5,3],[6,7,4],[8,9,5],[10,11,6],[12,13,7],[14,15,2],[14,16,2],[14,17,2],[14,18,2]]

• @Stomach_ache
It's 11, I just got it. it takes several minutes to compute.

• @fatalme

ohhh, yeah, it's correct.

• Thanks for the idea, made some improvement, got accepted, 35ms.

``````public int minTransfers(int[][] transactions) {
Map<Integer, Integer> net = new HashMap<>();
for (int[] t : transactions) {
net.put(t[0], net.getOrDefault(t[0], 0) - t[2]);
net.put(t[1], net.getOrDefault(t[1], 0) + t[2]);
}
int[] a = new int[net.size()];
int cnt = 0;
for (int v : net.values()) {
if (v != 0) a[cnt++] = v;
}
return helper(a, 0, cnt, 0);
}
int helper(int[] a, int start, int n, int num) {
int ans = Integer.MAX_VALUE;
while(start < n && a[start] == 0) start++;
for (int i = start + 1; i < n; ++i) {
if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
a[i] += a[start];
ans = Math.min(ans, helper(a, start + 1, n, num + 1));
a[i] -= a[start];
}
}
return ans == Integer.MAX_VALUE ? num : ans;
}
``````

• @iaming

A modified version of the C++ version, only takes 8ms:

``````public class Solution {

public int minTransfers(int[][] trans) {

Map<Integer, Integer> map = new HashMap<>();
for(int[] t : trans){
map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
}
int[] a = new int[map.size()];
int len = 0;
for(int v : map.values()){
if(v != 0){
a[len++] = v;
}
}

if(len == 0) return 0;

int[] dp = new int[1 << len];
Arrays.fill(dp, Integer.MAX_VALUE/2);
//System.out.println(Arrays.toString(a));
for(int i = 1; i < dp.length; i++){

int sum = 0, count = 0;
for(int j = 0; j < len; j++){
if((1<<j & i) != 0){
sum += a[j];
count++;
}
}

if(sum == 0){
dp[i] = count - 1;
for(int j = 1; j < i; j++){
if(((i & j) == j) && dp[j] + dp[i-j] < dp[i]) dp[i] = dp[j] + dp[i - j];
}
}

}

return dp[dp.length - 1];

}
}
``````

• @fatalme great, this is better, O(2^2n).

• public int minTransfers(int[][] transactions) {
Map<Integer, Integer> net = new HashMap<>();
for (int[] t : transactions) {
net.put(t[0], net.getOrDefault(t[0], 0) - t[2]);
net.put(t[1], net.getOrDefault(t[1], 0) + t[2]);
}
int[] a = new int[net.size()];
int cnt = 0;
for (int v : net.values()) {
if (v != 0) a[cnt++] = v;
}
return helper(a, 0, cnt, 0);
}
int helper(int[] a, int start, int n, int num) {
int ans = Integer.MAX_VALUE;
while(start < n && a[start] == 0) start++;
for (int i = start + 1; i < n; ++i) {
if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
a[i] += a[start];
ans = Math.min(ans, helper(a, start + 1, n, num + 1));
a[i] -= a[start];
}
}
return ans == Integer.MAX_VALUE ? num : ans;
}

I tried the following test case with your solution:
{{1, 8, 1}, {1, 9, 1}, {1, 1000, 1},{2, 8, 10}, {1, 400, 950}, {3, 9, 20}, {4, 10, 30}, {5, 11, 40}, {6, 12, 50}, {7, 13, 60}, {20, 80, 10}, {30, 90, 20}, {40, 100, 30}, {50, 110, 40}, {60, 120, 50}, {70, 130, 60}, {200, 800, 100}, {300, 900, 100}, {400, 1000, 1000}, {500, 1100, 10}, {600, 1200, 10}, {700, 1300, 10}}
The program has already taken hours and is still running....

• @yuhaowang001 That is how big n! is, try the 2^2n one.

• @yuhaowang001
Yes, it is that slow, I have optimized the code, and now it takes only 2 days. ;-). And the result is correct:

``````public class OptimalAccountBalancing {
public int minTransfers(int[][] trans) {
Map<Integer, Integer> net = new HashMap<>();
for(int i = 0; i < trans.length; i++){
net.put(trans[i][0], net.getOrDefault(trans[i][0], 0) - trans[i][2]);
net.put(trans[i][1], net.getOrDefault(trans[i][1], 0) + trans[i][2]);
}
int[] temp = new int[net.size()];
int i = 0;
for(int j : net.values()){
if(j != 0)temp[i++] = j;
}
int[] a = new int[i];
System.arraycopy(temp, 0, a, 0, i);

if(a.length == 0){
return 0;
}else if(a.length == 2) {
return 1;
}

number = Integer.MAX_VALUE;
mintran(a, 0, new int[]{0});
return number;
}

private int number = Integer.MAX_VALUE;

private void mintran(int[] a, int start, int[] res){
//System.out.println(Arrays.toString(a));
if(res[0] >= number) return;
if(number == (a.length + 1)/2) return;

int ind = -1;
int max = Integer.MIN_VALUE;
int i = start;
for(; i < a.length; i++){
if(Math.abs(a[i]) > max){
max = Math.abs(a[i]);
ind = i;
}
}

if(max == 0 || start == a.length){
if(res[0] < number){
number = res[0];
System.out.println(number);
}
return;
}

int temp = a[ind];
a[ind] = a[start];
a[start] = temp;

for(i = start + 1; i < a.length; i++){
temp = a[i];
if(a[i] * a[start] < 0) {
a[i] += a[start];
res[0]++;
mintran(a, start + 1, res);
res[0]--;
a[i] = temp;
}
}

temp = a[ind];
a[ind] = a[start];
a[start] = temp;

}

public static void main(String[] args) {
int[][] A = new int[][] {{1, 8, 1}, {1, 9, 1}, {2, 8, 10}, {3, 9, 20}, {4, 10, 30}, {5, 11, 40}, {6, 12, 50}, {7, 13, 60}, {20, 80, 10}, {30, 90, 20}, {40, 100, 30}, {50, 110, 40}, {60, 120, 50}, {70, 130, 60}};
OptimalAccountBalancing solution = new OptimalAccountBalancing();
System.out.println(solution.minTransfers(A));
}
}

``````

• Thanks folks for sharing the solution. Really like the idea of using for(int i = 1; i < state; i++) to loop through all possible subsets of current 'state'. My code got TLE as well, as I used very inefficient HashMap to record answer of subsets, recursion to obtain all possible subsets, and String to represent different subsets. The answer it provides is correct though.

``````    public int minTransfers(int[][] transactions) {
if(transactions == null || transactions.length == 0) return 0;
Map<Integer, Long> map = new HashMap<>();
for(int[] tran : transactions) {
map.put(tran[0], map.getOrDefault(tran[0], 0L) + (long)tran[2]);
map.put(tran[1], map.getOrDefault(tran[1], 0L) - (long)tran[2]);
}
List<Long> nums = new ArrayList<>(map.size());
for(Map.Entry<Integer, Long> entry : map.entrySet()) {
long total = entry.getValue();
}
int n = nums.size();
if(n == 0) return 0;
Map<String, long[]> dp = new HashMap<>();
List<Integer> set = new ArrayList<>(n);
for(int i = 0; i < n; i++) set.add(i);
return (int)helper(nums, set, dp)[0];
}
private long[] helper(List<Long> nums, List<Integer> set, Map<String, long[]> dp) {
String state = iString(set);
long[] res = dp.get(state);
if(res != null) return res;
res = new long[2];
if(set.size() == 1) {
res[0] = 0;
res[1] = nums.get(set.get(0));
dp.put(state, res);
return res;
}
List<Integer> temp = new ArrayList<>();
List<List<Integer>> permutaion = new ArrayList<>();
permute(set, 0, temp, permutaion);
long min = Integer.MAX_VALUE;
//System.out.println(permutaion + " " + set);
for(List<Integer> perm : permutaion) {
List<Integer> other = flip(set, perm);
long[] left = helper(nums, perm, dp);
long[] right = helper(nums, other, dp);
long total = left[0] + right[0];
total += left[1] == 0 || right[1] == 0 ? 0 : 1;
min = Math.min(min, total);
}
long sum = 0;
for(int idx : set) sum += nums.get(idx);
res[0] = min;
res[1] = sum;
dp.put(state, res);
return res;
}
private void permute(List<Integer> indices, int i, List<Integer> temp, List<List<Integer>> res) {
if(i == indices.size()) {
if(!temp.isEmpty() && temp.size() < indices.size()) res.add(new ArrayList<Integer>(temp));
return;
}
permute(indices, i + 1, temp, res);
permute(indices, i + 1, temp, res);
temp.remove(temp.size() - 1);
return;
}
private List<Integer> flip(List<Integer> indices, List<Integer> set) {
List<Integer> res = new ArrayList<>();
int j = 0;
for(int i = 0; i < set.size(); i++) {
j++;
}
return res;
}
private String iString(List<Integer> list) {
StringBuilder sb = new StringBuilder(list.size() * 2);
for(int i : list) {
sb.append(i);
sb.append('#');
}
return sb.toString();
}
``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.