Minimum additions

Rajnish

 Problem:-

You are given an array 

A

 of 

N

 positive integers. Your task is to add a minimum number of non-negative integers to the array such that the floor of an average of array 

A

 becomes less than or equal to 

K

.

The floor of an average of array 

A

 containing 

N

 integers is equal to 

⌊∑i=1NAiN⌋

. Here 

⌊.⌋

 is the floor function. You are given 

T

 test cases.

Input format

  • The first line contains a single integer 
    T

     that denotes the number of test cases. For each test case:

    • The first line contains two space-separated integers 
      N

       and 

      K

       denoting the length of the array and the required bound.

    • The second line contains 
      N

       space-separated integers denoting the integer array 

      A

Output format

For each test case (in a separate line), print the minimum number of non-negative integers that should be added to array 

A

 such that the floor of an average of array 

A

 is less than or equal to 

K

.

Constraints

1≤T≤101≤N≤2×1051≤A[i]≤1090≤K≤109

Sample Input
2
2 1
3 1
2 2
2 1
Sample Output
1
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we have 

N=2

, 

K=1

, 

A=[3,1]

. The current floor of average of 

A

 is 

⌊3+12⌋=2>K

.

If we add the element 

1

 to the array, the array becomes 

[3,1,1]

. The floor of average of 

A

 is 

⌊3+1+13⌋=1≤K

. Therefore, the minimum number of non-negative integers we need to add in this case is 

1

.

In the second test case, we have 

N=2

, 

K=2

, 

A=[2,1]

. The current floor of average of 

A

 is 

⌊2+12⌋=1≤K

. Therefore, we don’t need to add any non-negative integer to 

A

.

(c++)   Code:-

#include <iostream>
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
int main() {

    // this is for decreasing time
    // three lines use only for decrease time
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
cout.tie(NULL);
    int T;
    long long int N,K;
    cin >> T;   
    while(T–){
        cin >> N >> K;
        long long int i, temp, sum=0;
        for(i=0; i<N; i++){
            cin >> temp;
            sum+=temp;
        }
        long long int floor;
        floor = sum/N;
        if(floor <= K)
            cout << 0 << endl;
        else{
            long long int R = 1e18,extra,L=N,mid;
            while(L<=R){
                mid = (L+R)/2;
                floor = sum/mid;
                if(floor <= K){
                    extra = mid;
                    R = mid–1;
                }
                else{   
                    L = mid+1;
                }
            }
            cout << extra–N << endl;
        }
    }
}






Leave a Reply

Your email address will not be published.