You are given a sequence of positive integers A1,A2,…,AN and K, you can replace at most K element of sequence with any positive integer.
and check whether it is achievable or not A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN .
- Sort the given sequence of numbers in descending order.
- Replace first K elements with 1.
- check whether it is achievable or not A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN .
You are given a sequence of positive integers A1,A2,…,AN and K.
Here we need to minimize the numbers which are large enough because contribution of large numbers to make given condition false than the small number.
A12+A22+⋯+AN2 ≤ A1+A2+⋯+AN
in this equation we need to minimize the sum of squares so after sorting the given sequence of integers in descending order we can replace first K elements with 1 because 12 = 1, we can’t get minimum than this.
Check whether given condition is true or not.
Time complexity is O(N*log(N)) per test case.
Editorialist’s solution can be found here.
Feel free to Share your approach, If it differs. Suggestions are always welcomed.