# Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition

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?

• I just realized that this question can be considered about math only, even if there is a flavor of algorithm. Commented Apr 25, 2023 at 19:50

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$$.

• This is indeed a solution to a hackerrank problem "Permuting Two Arrays" and it works for all cases! It's weird.
– Avv
Commented Apr 25, 2023 at 20:20
• 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$. Commented Apr 25, 2023 at 20:43
• @Avv Where are the problem and that solution on HackerRank? Commented Apr 25, 2023 at 20:45
• Here is the solution link hackerrank.com/challenges/two-arrays/forum/comments/1254159. If you submit it, it will work with all cases.
– Avv
Commented Apr 25, 2023 at 20:47
• @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..."
– JimN
Commented Apr 25, 2023 at 22:35