I have an array of N numbers, and M swaps. Each swap has an index i and amount it subtracts from the ith number, and an index j and amount it adds to the jth number. It can only be applied if the current number at index i is greater than the amount that would be subtracted from it with the swap

From an arbitrary starting array N, I want to determine if there is an ordering that allows the M swaps can be applied, and if so what is one of the orderings. What is an efficient algorithm for this?

  • 2
    $\begingroup$ What does "current if number" mean? Is "if" an extra word? Where did you encounter this task? Can you credit the original source? What is the fastest algorithm you know of? I encourage you to edit your question to improve it. $\endgroup$
    – D.W.
    Commented Jul 7 at 0:49
  • 1
    $\begingroup$ What have you tried so far? Assuming I understood the problem correctly, the solution is trivial: apply the $M$ swaps on an array with all zeros, and for any index $i$, note the minimum this index's value has to go to. Using that you can greedily try to order the starting array $\endgroup$
    – EnEm
    Commented Jul 7 at 2:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.