Header Ads Widget

Ticker

6/recent/ticker-posts

Minimum additions

 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

1T101N2×1051A[i]1090K109

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=2K=1A=[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=1K. 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=2K=2A=[2,1]. The current floor of average of A is 2+12=1K. 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;
        }
    }
}






Post a Comment

0 Comments