Given a sequence A of length N, by changing at most K elements, can we make A_1^2+A_2^2+A_3^2 \dots A_N^2 \leq A_1+A_2+A_3 \dots A_N?
SUPER QUICK EXPLANATION
Count number of A[i] > 1, say C. If C \leq K, we can achieve inequality, otherwise no.
EXPLANATION
First of all, It can be seen that for every integer X, X \leq X^2. So, we can prove that we can never achieve A_1^2+A_2^2+A_3^2 \dots A_N^2 < A_1+A_2+A_3 \dots A_N.
Only option is, to achieve A_1^2+A_2^2+A_3^2 \dots A_N^2 == A_1+A_2+A_3 \dots A_N.
Now, Let’s find all integers, for which X^2 == X. We can find, that This holds for only X = 0 and X = 1. But we can assign only positive values to elements. Hence, to achieve this inequality, we need all elements to be 1.
Hence, just count the number of elements greater than 1 and if this count is \leq K, we can achieve this inequality, otherwise, we cannot achieve.
Challenge
Find any real value for which X^2 < X. Enjoy solving.
Minimum value for k is 1 ,1 \leq K \leq N \leq 10^4
So if initially suppose all numbers are one,for eg. n=3k=2A=\{1,1,1\}
Now because minimum value of k is 1 not zero so in all cases we have to consider value of k=1
But non 1 number count is zero as all three numbers are 1 from example above.
so according to your solution result should be YES.
But as we have to consider at least k=1
So your solution fails as changing any of the three 1’s to other value will not yield the desired result.
@setters and testers,
sorry dude, but your algorithm fails at certain test cases. as you just counting the elements which are not ones.
just try your algorithm on my testcase
N = 5, K = 2;
A[] = {1, 2, 3, 5, 8}
sum = 1 + 2 + 3 + 5 + 8 = 19
your algo shows NO for this…
I am just sorting array in reverse order,
so now array will be : A[] = {8, 5, 3, 2, 1}
replace K (2 in this case) elements from start by 1.
now array becomes A[] = {1, 1, 3, 2, 1}
and sum of squares = 1 + 1 + 9 + 4 + 1 = 16, which is less than 19, i.e. answer will be “YES” instead of “NO”.