Looks that this is a wrong question. The expected solution didn't consider this case.


  • 16
    T

    Given the input [[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]]

    The provided expected result is 14. However, there are only 11 transactions, so the upper bound of the result should be 11.


  • 5
    P

    I have the same doubt.
    since the code below passes all the test cases.

    class Solution {
    public:
        int minTransfers(vector<vector<int>>& transactions) {
            unordered_map<int,int> cnt;
            for(auto vec:transactions){
                cnt[vec[0]] += vec[2];
                cnt[vec[1]] -= vec[2];
            }
            priority_queue<int> pos,neg;
            int ans = 0;
            for(auto p:cnt){
                if(p.second>0) pos.push(p.second);
                if(p.second<0) neg.push(-p.second);
            }
            while(!pos.empty()){
                int po = pos.top(),ne = neg.top();
                pos.pop();
                neg.pop();
                ++ans;
                if(po>ne) pos.push(po-ne);
                else neg.push(ne-po);
            }
            return ans;
        }
    };
    

    But it obviously wrong. If the positive and negative balances are {4,4,5} and {5,8}, the minimum number of transaction needed is 3, but the code gives four.


  • 4
    N

    Yes, this question is obviously wrong. It should be a NPC problem.


  • 3
    P

    @nyunyunyunyu The standard solution is using greedy, but it is obviously wrong!


  • 1
    Q

    I think the tests for this problem are wrong. I got 11 too. Also, I got wrong answer in this test:

    [[8,23,20],[3,24,78],[4,20,37],[0,29,66],[2,29,2],[0,20,23],[0,22,65],[5,24,34],[0,27,6],[6,21,16],[1,26,2],[4,21,73],[8,27,64],[6,27,39],[5,25,15],[5,23,28],[8,25,53],[6,27,98],[0,25,92],[5,28,91],[8,21,75],[1,25,39],[1,22,55],[1,25,14],[4,26,70],[6,29,30],[6,26,11],[1,28,68],[1,26,13],[7,21,4],[3,29,77],[0,26,93],[7,20,39],[5,22,91],[9,27,80],[1,23,71],[6,29,27],[8,26,95],[8,29,24],[7,25,70],[1,29,17],[9,29,98],[6,22,26],[1,24,74],[0,25,33],[0,24,68],[8,25,91],[8,23,36],[1,29,25],[8,27,82],[4,24,14]]

    Base on this transaction, the list of deficit account and of surplus account are:

    [99, 155, 159, 168, 237, 268, 284, 366, 369, 407]
    [2, 113, 155, 178, 194, 247, 259, 378, 446, 540]

    The expected result is 19. However, we need only 18 transaction. First, the one with the deficit of 155 deficit pay directly to the one with the surplus of 155. Then the other 9 people with deficit all pay to the one with surplus of 2. Then he can distribute to 8 other people with surplus. So, the total transaction is only 18.


  • 1

    Same doubt.

    My code is like this.
    (It is not a correct answer though since I only considered 2-sum situation. There should be 3-sum, 4-sum, ...)

    class Solution(object):
        def minTransfers(self, transactions):
            """
            :type transactions: List[List[int]]
            :rtype: int
            """
            d = {}
            for trans in transactions:
                i, j, k = trans
                d[i] = d.get(i, 0) - k
                d[j] = d.get(j, 0) + k
    
            t = []
            for key in d:
                if d[key] != 0:
                    t.append(d[key])
            print (t), len(t)
    
            res = 0
            dt = {}
            for x in t:
                if x in dt:
                    print x
                    res += 1
                    if dt[x] == 1:
                        dt.pop(x)
                    else:
                        dt[x] -= 1
                else:
                    dt[-x] = dt.get(-x, 0) + 1
            s=0
            print res, dt, len(dt)
            for key in dt:
                s += dt[key]
            print s
            res += s-1 if s else 0
            return res
    

    In this test case:

    [[8,23,20],[3,24,78],[4,20,37],[0,29,66],[2,29,2],[0,20,23],[0,22,65],[5,24,34],[0,27,6],[6,21,16],[1,26,2],[4,21,73],[8,27,64],[6,27,39],[5,25,15],[5,23,28],[8,25,53],[6,27,98],[0,25,92],[5,28,91],[8,21,75],[1,25,39],[1,22,55],[1,25,14],[4,26,70],[6,29,30],[6,26,11],[1,28,68],[1,26,13],[7,21,4],[3,29,77],[0,26,93],[7,20,39],[5,22,91],[9,27,80],[1,23,71],[6,29,27],[8,26,95],[8,29,24],[7,25,70],[1,29,17],[9,29,98],[6,22,26],[1,24,74],[0,25,33],[0,24,68],[8,25,91],[8,23,36],[1,29,25],[8,27,82],[4,24,14]]
    

    The remaining non-zero balances are:

    [-446, -378, -2, -155, -194, -259, -247, -113, -540, -178, 99, 168, 237, 155, 268, 407, 284, 369, 159, 366]
    

    20 elements in this list, where +155 and -155 can form a pair.

    So there are 18 non-zero balances remain:

    {-159: 1, 194: 1, 259: 1, -284: 1, -407: 1, 2: 1, -369: 1, 113: 1, 178: 1, -237: 1, -268: 1, -366: 1, 247: 1, -168: 1, 378: 1, 540: 1, -99: 1, 446: 1} 
    

    which can be settled in 17 times.
    The total time should be 1+17=18 but the expected answer is 19.

    Is there any problem? I don't think it is correct, at least in this case.


  • 3
    Q

    Basically if we have m people with deficit and n people with surplus then the upper bound of the total necessary transactions is m+n-1. When ever we find a surplus balance equal to the sum of several deficit balances, we can reduce the upper bound by 1. But it's impossible to find the maximum number of surplus balances that can be decomposed into the sum of several disjoint sets of deficit balances. This is a NPC problem


  • 1

    @quanhoang The same.


  • 2
    K

    It is a NPC problem.
    Greedy will not work in this case.

    Consider,
    balance: [200, 100, 1, -50, -50, -50, -50, -101]
    Greedy will give us transaction of 7, while the actual good transaction number is 6.


  • 10
    K

    I have found a paper talking about this.
    The question can be transferred to a 3-partition problem, which is NP-hard.
    http://www.mathmeth.com/tom/files/settling-debts.pdf


  • 0
    S

    Some of the accepted solutions are using max heap, while some using min heap. I can't get neither of their idea... Is there any proof?


  • 0
    Z

    Up to UPDATE: (1:13am), an apparently wrong solution could still pass the OJ. Need more test cases.


  • 0

    @zizhengwu We've just rejudged the contest submissions again and most incorrect solution will get Wrong answer. Please let me know if you still find incorrect solution getting Accepted.


  • 0
    Z
    This post is deleted!

  • 0

    @1337c0d3r
    This code can pass the test. But it can not give correct answer with this case:
    [[0,3,9],[1,4,2],[2,5,5],[3,4,6],[4,5,2]]

    class Solution {
    public:
        void findAndRemoveOppositePair(map<int, int>& mm, int& res) {
            vector<int> removeVal;
            auto it = mm.begin();
            while(it != mm.end()) {
                int val = it->first;
                if(mm[val] > 0 && mm.find(-val) != mm.end() && mm[-val] > 0) {
                    if(--mm[val] == 0) removeVal.push_back(val);
                    if(--mm[-val] == 0) removeVal.push_back(-val);
                    res++;
                }
                it++;
            }
            
            for(int i = 0; i < removeVal.size(); i++) {
                mm.erase(removeVal[i]);
            }
            removeVal.clear();
        }
        
        int minTransfers(vector<vector<int>>& transactions) {
            if(transactions.empty()) return 0;
            map<int, int> acc;
            // first step: calculate diff
            for(int i = 0; i < transactions.size(); i++) {
                int id1 = transactions[i][0];
                int id2 = transactions[i][1];
                int money = transactions[i][2];
                acc[id1] -= money;
                acc[id2] += money;
            }
            
            int res = 0;
            map<int, int> mm;
            for(auto it : acc) {
                if(it.second != 0) {
                    mm[it.second]++;
                }
            }
            
            // divide exactly
            if(mm.size() == 2 && (mm.rbegin()->first % (-mm.begin()->first) == 0 || (-mm.begin()->first) % mm.rbegin()->first == 0)) {
                return max(mm.begin()->second, mm.rbegin()->second);
            }
            
            findAndRemoveOppositePair(mm, res);
            // turn all map values that are larger than 1 to 1
            for(auto it : mm) {
                int firstVal = it.first;
                int secondVal = it.second;
                if(secondVal > 1) {
                    mm[firstVal * secondVal] += 1;
                    mm.erase(firstVal);
                    res += (secondVal-1);
                }
            }
            findAndRemoveOppositePair(mm, res);
            
            while(!mm.empty()) {
                int iter1Key = mm.begin()->first;
                int iter2Key = mm.rbegin()->first;
                int iter1Val = mm.begin()->second;
                int iter2Val = mm.rbegin()->second;
                
                if(abs(iter1Key) > abs(iter2Key)) { // abs(neg) > abs(pos), iter1Key change
                    if(--mm[iter2Key] == 0) {
                        mm.erase(iter2Key);
                    }
                    mm.erase(iter1Key);
                    int newKey = iter1Key + iter2Key;
                    mm[newKey] += iter1Val;
                    res++;
                    if(mm.find(-newKey) != mm.end()) {
                        if(--mm[newKey] == 0) mm.erase(newKey);
                        if(--mm[-newKey] == 0) mm.erase(-newKey);
                        res++;
                    }
                } else {    // abs(pos) > abs(neg), iter2Key change
                    if(--mm[iter1Key] == 0) {
                        mm.erase(iter1Key);
                    }
                    mm.erase(iter2Key);
                    int newKey = iter1Key + iter2Key;
                    mm[newKey] += iter2Val;
                    res++;
                    if(mm.find(-newKey) != mm.end()) {
                        if(--mm[newKey] == 0) mm.erase(newKey);
                        if(--mm[-newKey] == 0) mm.erase(-newKey);
                        res++;
                    }
                }
            }
            return res;
        }
    };
    

  • 0

    @yong.cao.7731 Thanks, I have just added your test case.


  • 0
    H

    NPC problem, have to try all possible combinations with DFS to find out the best answer.

    Below solution is based on @tjmd012 post

    But it takes much time when the arrays size is slightly bigger. A way to optimize might be to do N-Sum (1 to max(borrower, lender) - 1) first to reduce the array size. Sort arrays before call dfs may also help.

    class Solution {
    public:
        int minTransfers(vector<vector<int>>& transactions) {
            unordered_map<int, int> m;
            for (auto t : transactions) {
                m[t[0]] -= t[2];
                m[t[1]] += t[2];
            }
            vector<int> borrower;
            vector<int> lender;
            for (auto& x : m) {
                if (x.second > 0) borrower.push_back(x.second);
                if (x.second < 0) lender.push_back(-x.second);
            }
    
            // for (auto x : borrower) cout << x << ","; cout << endl;        
            // for (auto x : lender) cout << x << ","; cout << endl;
            
            return dfs(borrower, lender, 0, 0);
        }
        
        int dfs(vector<int>& b, vector<int>& l, int bi, int li) {
            if (bi == b.size() || li == l.size()) return 0; // all set
            if (bi == b.size() - 1) return l.size() - li; // 1 borrower left, pay to remaining lenders
            if (li == l.size() -1 ) return b.size() - bi; // 1 lender left, remaining borrowers pay back
     
            int res = b.size() + l.size();
            for (int i = li; i < l.size(); i++) {
                if (l[i] == b[bi]) {
                    swap(l[li], l[i]);
                    res = min(res, dfs(b, l, bi+1, li+1) + 1);
                    swap(l[li], l[i]);
                    break;
                }
                else if (l[i] > b[bi]) {
                    l[i] -= b[bi];
                    res = min(res, dfs(b, l, bi+1, li) + 1);
                    l[i] += b[bi];
                }
                else {
                    b[bi] -= l[i];
                    swap(l[li], l[i]);
                    res = min(res, dfs(b, l, bi, li+1) + 1);
                    swap(l[li], l[i]);
                    b[bi] += l[i];
                }
            }
            return res;
        }
    };
    
    

  • 0
    D

    I only loop over lend and wrap around, and it is still accepted. If we can do this way, then we don't need to use backtracking. I doubt it.

        int minTransfers(vector<vector<int>>& transactions) {
            map<int, int> mp;
            for (auto& transaction : transactions) {
                mp[transaction[0]] += transaction[2];
                mp[transaction[1]] -= transaction[2];
            }
            vector<int> lend, borrow;
            for (auto& m : mp) {
                if (m.second < 0) borrow.push_back(-m.second);
                else if (m.second > 0) lend.push_back(m.second);
            }
            if (borrow.empty() && lend.empty()) return 0;
            int min_res = transactions.size();
            for (int loop = 0; loop < lend.size(); loop++) {
                int res = 0;
                int lend_left = 0, borrow_left = 0;            
                int i = 0, j = 0;
    	    while (i < lend.size() && j < borrow.size())
    	    {
    		lend_left = lend_left != 0 ? lend_left : lend[(i+loop)%lend.size()];
    		borrow_left = borrow_left != 0 ? borrow_left : borrow[j];
    		if (lend_left == borrow_left) {
    	            i++;
    		    j++;
    		    lend_left = 0;
    		    borrow_left = 0;
    		} else if (lend_left < borrow_left) {
    		    borrow_left = borrow_left - lend_left;
    		    i++;
    		    lend_left = 0;
    	        } else {
    		    lend_left = lend_left - borrow_left;
    		    j++;
    		    borrow_left = 0;
    		}
    		res++;
                }
                min_res = min(min_res, res);
            }
            return min_res;
        }
    
    

  • 0
    X

    My code's answer is 4. I used DFS in this problem


Log in to reply
 

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