Given an array **a** consisting of **n** elements, call array **b** consisting of **n** elements such that **(a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2 is minimum** and sum of all elements of array **B** is equal to **m**.

Given n, array A, m, find the value of (a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2.

Constraints : 1 <= n <= 1e5 , 1 <= m <= 2e9, 1 <= a[i] <= 2e9

Input : first line n,m respectively, second line is the elements of array A Output : the expected value

Ex:

Input : 3 3 3 4 5 Output : 27 Input : 10 4 2 3 4 5 Output : 4

Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).LOGIC::

The sum of the given expression will be minimum when each part of the sum is minimum. Greater numbers have greater squares, thus we decrease the greater numbers.

CODE ::

For the given array A, select the maximum element present, then decrease the element by 1. Repeat it "m" times. LOOP Then print the sum of squares of all elements of array A.

Thanks ^^, but actually this problem constrains is quite large, 1 <= m <= 2e9, 1 <= a[i] <= 2e9, (I've forgoten to write it in the post) Do you come up with some ideas to solve for the large m?

The official constraints of that problem is

1 <= n <= 1e5, 1 <= m <= 2e9, 1 <= a[i] <= 2e9

We here also find an array such that square of its elements is the answer. __ Take the sum of array A, __ from this minus the " m ". __ Now you have the sum of required array.

The logic used is same as above go to bottom for explanation

## as n < 10e5, the below solution has time complexity of O(n)

a = [Given array]

sum_of_a = sum(a)

sum_of_arr = (sum_of_a) — m

a.sort()

arr = []

for (i=0 ; i<=len(a) ;i++)

## the array arr must be the answer

calculate the sum of squares of array arr

******* Here we know the sum of the required array, so we just need the particular elements::

## the best case will be all elements are same and they are lesser than or equal to minimum of array A

## ** in other cases the other elements might be smaller

## ** so we append the smaller elements from array A.

## __ and we again go to try the best case for leftover (n-i) elements.

**** Q. What have we done?

When we get array arr, we observe that the maximum elements of A are decreased to an appropriate value and the rest of smaller elements remain same.

if any queries feel free to ask

Thanks a lot, now I could understand your idea ^^

It appears you can use Lagrange multipliers for this. The concept applies here, and I'm sure you can convert it into actual working code.

Auto comment: topic has been updated by adsijf (previous revision, new revision, compare).