1
$\begingroup$

Given 2 arrays $A, B$ each of size $n$. If we want to find if the two arrays satisfy the condition that $A[i] + B[i] \ge k$ for all indices $i$, it's sufficient to fulfill 3 conditions below:

  1. Sum of all elements of $A$ and $B$ is $\ge nk$
  2. Sum of max element of $A$ and min element of $B$ is $\ge k$ (edge case)
  3. Sum of min element of $A$ and max element of $B$ is $\ge k$ (edge case)

Edit: Based on answers, these 3 conditions are not sufficient to prove that they work with all cases please given that they don't go over elements in between edge cases?

$\endgroup$
1
  • 1
    $\begingroup$ I just realized that this question can be considered about math only, even if there is a flavor of algorithm. $\endgroup$
    – John L.
    Commented Apr 25, 2023 at 19:50

1 Answer 1

1
$\begingroup$

No, these 3 conditions are not sufficient.

For example, $n=4$, $A=[6,5,2,1]$, $B=[1,3,4,6]$, $k=7$.

  • The sum of all elements in $A$ and $B$ is $14+14=28=4\cdot7$.
  • The sum of the max in $A$ and the min in $B$ is $7$.
  • The sum of the min in $A$ and the max in $B$ is $7$.

However, $A[2]+B[2]=2+4=6<7$.

$\endgroup$
6
  • $\begingroup$ This is indeed a solution to a hackerrank problem "Permuting Two Arrays" and it works for all cases! It's weird. $\endgroup$
    – Avv
    Commented Apr 25, 2023 at 20:20
  • 1
    $\begingroup$ Another example. $n=5$, $\ A=[100,4,3,2,1]$, $\ B=[1,2,3,4,100]$, $\ k=44$. We have $A[i]+B[i]<44$ for all $i$ except the required cases $i=0,4$. $\endgroup$
    – John L.
    Commented Apr 25, 2023 at 20:43
  • 1
    $\begingroup$ @Avv Where are the problem and that solution on HackerRank? $\endgroup$
    – John L.
    Commented Apr 25, 2023 at 20:45
  • $\begingroup$ Here is the solution link hackerrank.com/challenges/two-arrays/forum/comments/1254159. If you submit it, it will work with all cases. $\endgroup$
    – Avv
    Commented Apr 25, 2023 at 20:47
  • 1
    $\begingroup$ @Avv their testcases are clearly insufficient (or incorrectly created) and the proposed solution fails on a small counterexamples provided here. You should probably write to the problem author hackerrank.com/profile/Khongor rather than here. Your original post should probably be modified to ask "are these three conditions sufficient..." rather than asking "why are these three conditions sufficient..." $\endgroup$
    – JimN
    Commented Apr 25, 2023 at 22:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.